ASSIGNMENT PROBLEM

Assignment problem - Choose an assignment of people to jobs so as to minimize total cost. The ordinary model is that of a matching problem . Although the usual assignment problem is solvable in polynomial time (as a linear program ), important extensions are the following NP-complete problems :

Quadratic assignment (QAP). The objective is a quadratic form , which can have just cross terms, so it need not be convex (in fact, it can be quasiconcave , in which case a solution occurs at an extreme point ). The QAP includes the traveling salesman problem as a special case (this is what is used with a neural network model of the TSP).

Multi-dimensional assignment. More than 2 indexes, the variables are of the form, X(i, j, k, ...). The constraints sum all but one index -- for example, the 3-index assignment problem is given by:

Min Sum _i,j,k(C(i, j, k) X(i, j, k)): X >= 0;

Sum _j,k(X(i, j, k)) = 1 for all i; Sum _i,k(X(i, j, k)) = 1 for all j; Sum _i,j(X(i, j, k)) = 1 for all k.