Assignment problem

The (linear) assignment problem is a discrete optimization problem from graph theory . It is a special, classic transport problem and is used in operations research .

It can be solved using linear programming or using the Hungarian method .

Problem Description

It can be formulated verbally as follows:

The same number of activities with known (execution) costs should be assigned to a number of workers, the execution costs differing from worker to worker and from task to task. ${\displaystyle n}$

• Each worker is assigned exactly one activity and each activity is carried out by exactly one worker.
• The lowest-cost work plan is then selected from among all the permitted plans.

Mathematical model

Description of graph theory

It is a bipartite, weighted graph with given. Between each node there is an edge, the weight of which represents the costs that arise if you match and . ${\displaystyle G=(L\cup R,E)}$ ${\displaystyle |L|=|R|=n}$ ${\displaystyle l\in L,r\in R}$ ${\displaystyle l}$ ${\displaystyle r}$

The goal is now to find a maximum matching with minimum costs.

Matrix display

Based on the problem description, we can generate a matrix by entering the costs in the cell that arise when we assign the task to the worker . ${\displaystyle n\times n}$ ${\displaystyle A\in \mathbb {R} ^{n,n}}$ ${\displaystyle a_{i,j}}$ ${\displaystyle i}$ ${\displaystyle j}$

The goal is then to find a permutation of the rows of the matrix that minimizes their trace .

Description as a linear program

With the variables (to be determined) ${\displaystyle x_{ij}}$

${\displaystyle x_{ij}={\begin{cases}1,&{\text{falls Arbeiter i die Tätigkeit j ausführen soll}}\\0,&{\text{sonst}}\end{cases}}}$

and the (given) execution costs, the following mathematical model results: ${\displaystyle c_{ij}}$

Minimize the total cost

${\displaystyle F=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}}$

under the constraints

${\displaystyle \sum _{j=1}^{n}x_{ij}=1}$for , ${\displaystyle i=1,\cdots ,n}$

${\displaystyle \sum _{i=1}^{n}x_{ij}=1}$for . ${\displaystyle j=1,\cdots ,n}$

Time complexity

The problem can be solved using the Hungarian method in . ${\displaystyle {\mathcal {O}}(n^{3})}$

Examples and effort

Examples of the linear assignment problem are the assignment of students to school projects or the assignment of students to seminar places.

For calculated examples see Hungarian method, examples .

Generalizations and Variants

The assignment problem is a special case of a maximum matching of minimum weight in a bipartite, weighted graph.

If only relative costs are known instead of absolute costs, this is a stable marriage problem .

literature

• A. Bogatzki: Factory planning: procedure for optimizing machine installation. Diss. University of Wuppertal 1998. Roderer, 1998, ISBN 3-89073-234-8 .
• Wolfgang Domschke , Andreas Drexl: Introduction to Operations Research . Springer, 2011, ISBN 978-3-642-18111-5 , pp. 188ff. ( Excerpt (Google) )

Web links

• Chapter transport optimization. (PDF; 516 kB). Script TU Freiberg, pp. 33-40.