Quadratic Assignment Problem¶
Optimize a one-to-one placement when the cost of one item-position choice depends on other simultaneous placements.
Core Idea¶
A quadratic assignment problem (QAP) assigns \(n\) items one-to-one to \(n\) positions while optimizing costs that depend on pairs of placements. Moving one item can change the cost associated with other items' placements. With binary \(x_{ij}\) for item \(i\) at position \(j\), one formulation sums \(C_{ikjl}x_{ij}x_{kl}\) over two item-position choices, subject to each item and position appearing exactly once. Lawler's general four-index coefficients include the Koopmans–Beckmann special form \(C_{ikjl}=F_{ik}D_{jl}\), which separates item interaction from position-pair cost.[ref-824ec8e7a25c][ref-d59c3a7dc5fa][^ref-20ee88dbb9da]
Scope of Application¶
Koopmans and Beckmann modeled plants assigned to sites: commodity flow between plants incurs a cost depending on their chosen locations, sometimes alongside independent plant-site profit. Steinberg's backboard problem places connected electronic components in board slots; a later original study maps wire counts and slot distances into a factorized QAP. In that analyzed benchmark, two dummy items make 34 components and 36 slots into an equal-size permutation problem. Neither application makes physical Euclidean distance a requirement of general QAP.[ref-824ec8e7a25c][ref-809a827a7e58][^ref-20ee88dbb9da]
Clarity¶
The decisive question is whether the cost of placing \(i\) at \(j\) changes when another item \(k\) moves. If all scores are independent item-position terms, the problem is linear assignment or a degenerate special case, not the distinctive pair-coupled QAP. A general Lawler coefficient need not factor into flow times distance; the Koopmans–Beckmann product is a useful subtype. A solver, a historical wiring instance and a claimed optimum are different from the problem class.[ref-824ec8e7a25c][ref-d59c3a7dc5fa]
Manages Complexity¶
Permutation variables and pair coefficients compress a large set of complete layouts into a testable optimization model. Factorized \(F\) and \(D\) expose who interacts and where interaction is expensive; general \(C\) preserves costs that cannot be separated. The model's economy comes with limits: capacities, multiway routing effects or different objectives require extensions, and a computed layout is not automatically certified optimal.[ref-d59c3a7dc5fa][ref-20ee88dbb9da]
Abstract Reasoning¶
Declare equal item and position sets (or justified dummy padding), the feasible bijections, and either the general joint coefficients \(C_{ikjl}\) or a verified product \(F_{ik}D_{jl}\). Evaluate the full placement objective, including any declared linear terms. A swap can change many pair contributions, which explains why independent local rankings can mislead. Methods such as bounds and exact search analyze an instance but are not constitutive of QAP itself.[ref-824ec8e7a25c][ref-d59c3a7dc5fa][^ref-20ee88dbb9da]
Knowledge Transfer¶
The plant and backboard cases share items, positions, bijection, pair interaction and an objective. Commodity flows do not become wires, and the cost metric or best permutation does not transfer between them. A broader “interdependent choices” pattern is a possible future-prime question; it is not established merely by dropping QAP's mathematical types.[ref-824ec8e7a25c][ref-20ee88dbb9da]
[^ref-824ec8e7a25c]: Tjalling C. Koopmans and Martin J. Beckmann, “Assignment Problems and the Location of Economic Activities,” Cowles Foundation Discussion Paper 4 (1955), Yale original scan, §§2 and 6; revised Econometrica 25(1):53–76 (1957). [^ref-d59c3a7dc5fa]: Eugene L. Lawler, “The Quadratic Assignment Problem,” Management Science 9(4):586–599 (1963), original publisher abstract. [^ref-809a827a7e58]: Leon Steinberg, “The Backboard Wiring Problem: A Placement Algorithm,” SIAM Review 3(1):37–50 (1961), original publisher record. [^ref-20ee88dbb9da]: Nathan W. Brixius and Kurt M. Anstreicher, “The Steinberg Wiring Problem,” original later research chapter, §§17.1–17.2 pp.293–295.
Relationships to Other Abstractions¶
Current abstraction Quadratic Assignment Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Quadratic Assignment Problem is a kind of Optimization Problem Domain-specific
QAP is an optimization problem over bijections with a pairwise placement objective.
Hierarchy path (1) — routes to 1 parentless root
- Quadratic Assignment Problem → Optimization Problem → Optimization
Neighborhood in Abstraction Space¶
Quadratic Assignment Problem sits in a moderately populated region (56th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Storage & Lookup Data Structures (21 abstractions)
Nearest neighbors
- Maximum Inner-Product Search — 0.88
- Matrix — 0.86
- Generalized blockmodeling of binary networks — 0.85
- GI (complexity) — 0.85
- GI-complete — 0.84
Computed from structural-signature embeddings · 2026-10-08