Assignment

We analyze the problem of assigning n people to n jobs. The value of person j in job i is $$X_{ij}^{\ast }$$, and let X* denote the n×n matrix of these values. The goal is to maximize the total value. The assignment of people to jobs is a permutation. A mathematical model of a permutation is an n×n matrix X, having components Xij. Each row has a single component one, and each column has a single component one. All other components are zero. Interpret Xij=1 as the assignment of person j to job i. The total value achieved by a permutation X is the linear function $$\left \langle {\textit {{\sf { {X}}}}}^{\ast },{\textit {{\sf { {X}}}}}\right \rangle$$. The assignment problem was important in the historical development of the theory of linear programming and duality. At first glance, it might seem that the problem is not a convex optimization. Choosing the optimum permutation from among the n! possible permutations is a choice among discrete alternatives, not a convex problem. Nevertheless, it is possible to cast the problem as an interesting convex optimization, having a dual with an insightful economic interpretation. A matrix is doubly stochastic if the sum of each column is one, and the sum of each row is one, and every component is nonnegative. A permutation is doubly stochastic, and any convex combination of permutations is doubly stochastic. Thus any doubly stochastic linear transformation is a convex combination of permutations. That the permutations are the extreme points of the set of doubly stochastic linear transformation is a fundamental theorem. Set the assignment problem as the maximization of$$~\left \langle {\textit {{\sf { {X}}}}}^{\ast },{\textit {{\sf { {X}}}}}\right \rangle$$ among all doubly stochastic linear transformations.