Assignment problem

The problem of optimally assigning $ m $ individuals to $ m $ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem:

maximize $ \sum _ {i,j } c _ {ij } x _ {ij } $

subject to

$$ \sum _ { j } x _ {ij } = a _ {i} , i = 1 \dots m $$

(origins or supply),

$$ \sum _ { i } x _ {ij } = b _ {j} , j = 1 \dots n $$

(destinations or demand), where $ x _ {ij } \geq 0 $ and $ \sum a _ {i} = \sum b _ {j} $, which is called the balance condition. The assignment problem arises when $ m = n $ and all $ a _ {i} $ and $ b _ {j} $ are $ 1 $.

If all $ a _ {i} $ and $ b _ {j} $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ {ij } $ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $ x _ {ij } $ is either zero or one; $ x _ {ij } = 1 $ means that person $ i $ is assigned to job $ j $; the weight $ c _ {ij } $ is the utility of person $ i $ assigned to job $ j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method. Some of these use the Hungarian method (see, e.g., [a5], [a1], Chapt. 7), which is based on the König–Egervary theorem (see König theorem), the method of potentials (see [a1], [a2]), the out-of-kilter algorithm (see, e.g., [a3]) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

References

[a1]	D.B. Yudin, E.G. Gol'shtein, "Linear programming" , Israel Program Sci. Transl. (1965) (In Russian)
[a2]	R. Frisch, "La résolution des problèmes de programme linéaire par la méthode du potentiel logarithmique" Cahier Sém. Econom. , 4 (1956) pp. 20–23
[a3]	K. Murtz, "Linear and combinatorial programming" , Wiley (1976)
[a4]	M. Grötschel, L. Lovász, A. Schrijver, "Geometric algorithms and combinatorial optimization" , Springer (1987)
[a5]	C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)