Quadratic assignment problem

From Glossary

Jump to: navigation, search

(QAP). See assignment problem.

Assignment problembutton.png

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

\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.
Personal tools