The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.
The problem models the following real-life problem:
- There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows.
Intuitively, the cost function encourages factories with high flows between each other to be placed close together.
The problem statement resembles that of the assignment problem, only the cost function is expressed in terms of quadratic inequalities, hence the name.
Read more about Quadratic Assignment Problem: Formal Mathematical Definition, Computational Complexity, Applications
Famous quotes containing the word problem:
“How much atonement is enough? The bombing must be allowed as at least part-payment: those of our young people who are concerned about the moral problem posed by the Allied air offensive should at least consider the moral problem that would have been posed if the German civilian population had not suffered at all.”
—Clive James (b. 1939)