(QAP). See 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, $LaTeX: x_{i,j,k, ...}$. The constraints sum all but one index -- for example, the 3-index assignment problem is

$LaTeX: \textstyle \begin{array}{rrcl} \min & \sum_{i,j,k} c_{i,j,k} x_{i,j,k} & & \\ \\ \mbox{s.t.} & \sum_{j,k} x_{i,j,k} & = & 1 \mbox{ for all } i, \\ & \sum_{i,k} x_{i,j,k} & = & 1 \mbox{ for all } j, \\ & \sum_{i,j} x_{i,j,k} & = & 1 \mbox{ for all } k. \end{array}$