Quadratic Assignment Problem (QAP)
The quadratic assignment problem (QAP) assigns facilities to locations when the cost depends on pairs of assignments—typically flow × distance. This interaction term makes QAP fundamentally harder than the linear assignment problem solved by the Hungarian algorithm.
If your costs depend only on single pairs (worker→job), you likely want the linear assignment family: assignment problem examples and Hungarian algorithm explained.
On this page
Quick takeaway: QAP assigns facilities to locations when cost depends on pairs: facilities that interact heavily (high flow) should be placed close (small distance). This interaction term makes QAP much harder than linear assignment.
What is the quadratic assignment problem?
A common story: you are designing a facility layout (departments in a plant, components on a chip, gates in an airport). You know:
- flow between facility pairs (how much they interact), and
- distance between location pairs (how far apart placements are).
The total cost depends on how interacting facilities are placed relative to each other, not just on a single facility’s location.
This “pairwise interaction” is exactly what breaks the Hungarian algorithm’s applicability.
Hungarian solves linear assignment where cost is Σ c(i,j) x(i,j).
Standard QAP formulation (flow × distance)
Let facilities be i,k and locations be j,l.
Let F[i,k] be the flow between facilities, and D[j,l] be the distance between locations.
Let x[i,j]=1 if facility i is placed at location j.
Classic QAP objective:
minimize Σ_i Σ_k Σ_j Σ_l F[i,k] * D[j,l] * x[i,j] * x[k,l]
Assignment constraints (still one-to-one):
Σ_j x[i,j] = 1 for each facility i
Σ_i x[i,j] = 1 for each location j
x[i,j] ∈ {0,1}
x[i,j] * x[k,l]. That product makes the model quadratic.
In practice, exact approaches often rely on integer programming machinery (branch-and-bound/branch-and-cut):
branch-and-bound.
QAP vs linear assignment (Hungarian)
Linear assignment (LAP)
Cost depends only on one decision: “assign worker i to job j.”
Objective is linear: Σ c(i,j) x(i,j).
Solve with: Hungarian algorithm.
Quadratic assignment (QAP)
Cost depends on pairs: “if facility i is at location j AND facility k is at location l, pay F(i,k)·D(j,l).” Objective is quadratic, typically much harder to solve.
If your problem is truly linear one-to-one, use the assignment cluster: examples, Python (SciPy), unbalanced (dummy).
Worked examples
Worked example
Example 1 (3×3): compute QAP cost for two layouts
Facilities: A, B, C. Locations: 1, 2, 3.
Flow matrix F (symmetric, 0 diagonal):
A B C A 0 5 2 B 5 0 3 C 2 3 0
Distance matrix D:
1 2 3 1 0 1 4 2 1 0 2 3 4 2 0
To avoid double counting, compute pair-sum over unordered pairs (A–B, A–C, B–C):
Cost = Σ_{i<k} F(i,k) · D(loc(i), loc(k)).
(Some texts use the full double-sum; then your value is doubled. The ranking of layouts is unchanged.)
Layout 1: A→1, B→2, C→3
- A–B: 5 · D(1,2)=5·1=5
- A–C: 2 · D(1,3)=2·4=8
- B–C: 3 · D(2,3)=3·2=6
Total = 5 + 8 + 6 = 19
Layout 2: A→2, B→1, C→3
- A–B: 5 · D(2,1)=5·1=5
- A–C: 2 · D(2,3)=2·2=4
- B–C: 3 · D(1,3)=3·4=12
Total = 5 + 4 + 12 = 21
Worked example
Example 2: Why “best individual costs” does not work for QAP
In linear assignment, you can think in terms of choosing low individual costs c(i,j).
In QAP, there is no single cost c(i,j) that captures the full effect of placing facility i at location j,
because the total depends on where every other facility is placed.
That’s why Hungarian (which is built for linear costs) cannot directly solve QAP.
Worked example
Example 3: Practical modeling boundary—when QAP appears in “scheduling”
QAP-style interaction costs show up when the cost of assigning A depends on where B goes too—for example:
- layout decisions (departments close together reduce travel),
- pairwise communication cost (teams placed on floors),
- routing adjacency penalties (components placed with interference considerations).
If your problem is one-to-one without interaction costs, see: job scheduling using assignment model.
How QAP is solved in practice
QAP is widely considered difficult at scale. Common approaches include:
- Exact methods for small instances: branch-and-bound / cutting planes / specialized QAP bounds.
- Heuristics/metaheuristics for larger instances: local search, tabu search, simulated annealing, GRASP, genetic algorithms.
- Mathematical programming formulations: MILP linearizations or MIQP forms (can be large).
If you’re learning exact integer optimization concepts used by solvers, start with branch-and-bound, optimality gap, and Gomory cuts.
Questions people ask
Questions people ask
Is QAP NP-hard?
In general, QAP is regarded as computationally difficult; exact solving can become intractable as size grows, so heuristics and bounds are common for larger instances.
Questions people ask
Is QAP the same as assignment problem?
QAP is a generalization. Linear assignment has linear costs c(i,j).
QAP has interaction costs depending on pairs of assignments.
Questions people ask
Can I solve QAP using the Hungarian algorithm?
Not directly. Hungarian solves linear assignment. QAP’s quadratic objective requires different methods (exact or heuristic).
Questions people ask
What is a typical application of QAP?
Facility layout problems are the classic application: assign departments to locations so high-flow pairs are close.
Questions people ask
How do I evaluate a candidate QAP solution?
Given a permutation (facility→location mapping), compute Σ_{i<k} F(i,k)·D(loc(i),loc(k))
(or the full double-sum variant). Example 1 above shows the step-by-step calculation.
What to do next
If your costs are linear (no interactions), you’re in the assignment family: Hungarian algorithm, assignment examples, Python (SciPy).
If you want to understand exact optimization machinery used for hard combinatorial problems, see ILP/MILP, branch-and-bound, and optimality gap.
Disclaimer
This QAP guide is for educational purposes. Real facility layout and interaction-cost models may require additional constraints (capacity, safety distances, adjacency rules, blocking, time dependence) not captured by the classic QAP form. Many QAP instances are computationally hard; heuristic solutions may be the only practical option at scale. Always validate assumptions, solution quality, and sensitivity before operational use. Read the full disclaimer.
Related guides
Sources
- Koopmans & Beckmann (1957) — Assignment Problems and the Location of Economic Activities (Econometrica)
- Burkard, Cela, Pardalos, Pitsoulis — The Quadratic Assignment Problem and Related Problems (Springer book page)
- QAPLIB — Benchmark library for QAP instances
- Burkard, Dell’Amico, Martello — Assignment Problems (SIAM book page; linear assignment background)
- Wikipedia — Quadratic assignment problem (overview)