Skip to content

Quadratic Assignment Problem

Optimize a one-to-one placement when the cost of one item-position choice depends on other simultaneous placements.

Version
v1 · 2026-10-03 · History
Domain-specific #
13538
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Combinatorial Optimization → Mathematics
Aliases
QAP

Core Idea

The quadratic assignment problem (QAP) asks how to assign \(n\) items one-to-one to \(n\) positions when the cost of a placement depends on where other items are placed. In an ordinary linear assignment, each item-position pair can be scored on its own. In QAP, a score can attach to the joint choice “item \(i\) goes to \(j\) and item \(k\) goes to \(l\).” The objective evaluates complete assignments and seeks a best one. A plant-location decision with interplant freight and a computer-backboard placement with intercomponent wires are unlike physical realizations of that same coupled-choice form.[1][2][3]

Let \(x_{ij}=1\) if item \(i\) occupies position \(j\), and $0$ otherwise, with each row and column summing to one. In a general Lawler-style formulation the pair cost is \(C_{ikjl}\) and the objective includes \(\sum_{i,k,j,l} C_{ikjl}x_{ij}x_{kl}\). The four-index coefficient can depend on the entire pair of simultaneous placements. In the narrower Koopmans–Beckmann form \(C_{ikjl}=F_{ik}D_{jl}\): \(F\) records interaction or flow between items and \(D\) records a cost associated with the two chosen positions. Optional independent assignment terms \(\sum_{ij}A_{ij}x_{ij}\) can be included without erasing the quadratic interaction. The original Koopmans–Beckmann location paper combined individual plant-location profit with interplant transportation cost; Lawler explicitly identified it as a special case of his more general problem.[1][2][3]

QAP is not defined by any particular algorithm, hardness slogan, physical distance metric or application. Its autonomous abstraction is the permutation with pair-dependent score: changing one assignment can alter the contribution of several other assignments, so local rankings alone are insufficient in general.

Structural Signature

Sig role-phrases: \(n\) items → \(n\) positions → bijection/permutation → joint pair-placement coefficients → objective over complete assignments; flow-times-distance is a special factorization.

  • Items. The objects to place are indexed \(i,k\in\{1,\ldots,n\}\). Plants and electronic components differ materially but serve the same item role.[1][3]
  • Positions. The receiving sites \(j,l\) are distinct slots. The standard QAP assumes equal cardinality and one item per slot; unequal numbers can sometimes be padded with dummy items, as Brixius and Anstreicher do for Steinberg's backboard benchmark, but padding must be declared.[3]
  • Bijection. Binary \(x_{ij}\) obey \(\sum_j x_{ij}=1\) for each item and \(\sum_i x_{ij}=1\) for each position. Thus a feasible solution is a permutation matrix, not merely a collection of pair scores.[1][3]
  • Joint pair-placement coefficients. \(C_{ikjl}\) scores two assignments together. It can represent item-pair flow times position-pair cost when factorized, but Lawler's general form need not separate that way. The mathematics requires a coefficient for the joint placement, not necessarily Euclidean separation.[2][3]
  • Objective over permutations. Sum the appropriate pair contributions and minimize modeled cost (or maximize a declared net payoff). A single-placement linear term may coexist with the quadratic part.[1][3]
  • Subtype factorization. \(F_{ik}D_{jl}\) has interpretable item interactions and positional costs. It is diagnostic for a Koopmans–Beckmann instance, not a condition for every Lawler QAP.[2][3]

What It Is Not

It is not merely linear assignment in harder notation. If every item's contribution depends only on its own selected position, an independent-score assignment model suffices. In the quadratic case, the marginal effect of moving plant \(i\) depends on where plant \(k\) is, because their transport term changes. Lawler notes that a quadratic model can be transformed into a linear assignment with additional constraints; that is a reformulation, not proof that the original pair-dependence has vanished.[1][2]

It is not necessarily a physical-distance problem. A position-pair matrix may encode travel cost, wiring length under a chosen norm, latency or another declared interaction cost. The fully general four-index \(C\) need not even factor into an item matrix and position matrix. Calling every coefficient “distance” would incorrectly narrow the formal identity.[2][3]

It is not the Steinberg benchmark, a hospital plan, or a solver. A named instance fixes specific data; an algorithm searches the feasible permutations; an optimum is the result. None alone is the reusable problem class. Nor does the class justify the seed's blanket claims that all instances have one approximation status or that exact solution is impossible beyond a fixed size.

Scope of Application

The standard formulation applies to equal-sized sets with one-to-one placement and an objective containing joint pair-placement contributions. Koopmans and Beckmann modeled indivisible economic activities allocated to locations with interplant commodity flow; their quadratic terms captured transport interactions that independent plant-location profit could not. The same formal roles can be declared for backboard wiring: connected components are placed in board slots and pairs incur wiring cost according to connectivity and slot separation.[1][4][3]

The scope has boundaries. Different capacities, several items per site, unassigned items or dynamic relocations require altered feasible sets. A bottleneck objective that minimizes a maximum pair cost rather than their sum defines a variant, not an unqualified instance of the summed QAP used here. In a real layout the chosen pairwise distance model may omit routing congestion and obstacle geometry; solving the formal instance then optimizes its stated surrogate, not necessarily the entire physical design.

Clarity

The most compact diagnostic is counterfactual: Would the cost attributed to placing \(i\) at \(j\) change if a different item \(k\) moved from \(l\) to \(m\)? If yes through \(C_{ikjl}\) versus \(C_{ikjm}\), the objective couples placements. If not, the supposed quadratic expression might reduce to independent costs. This diagnostic identifies the residual without treating “quadratic” as a synonym for computationally difficult.[1][2]

The model should declare whether \(C\) is general, factorized as \(F D\), symmetric or directed, and whether it includes a linear assignment term. In the original plant-location problem, assigning each plant to a site can bring an individual profit as well as pairwise transportation charges; suppressing the linear term when explaining that original formulation would misstate it. Conversely, a cost-only Koopmans–Beckmann instance can omit it by design.[1][3]

Manages Complexity

The QAP abstraction compresses a huge table of complete placement outcomes into a permutation and local pair contributions. In the factorized form, two \(n\times n\) matrices expose why heavily interacting items should be considered relative to expensive position pairs. In the general form, four-index coefficients allow interactions that cannot be described by that simple product. The framework therefore lets the analyst compare plant and wiring examples without pretending their units, metrics or constraints are identical.[2][3]

The compression has a cost. A pairwise objective assumes all relevant effects can be represented as sums of pair contributions, optionally with single-placement terms. Multiway congestion, route sharing, capacity limits and time-varying demand may require a different or extended model. Even when the formulation is appropriate, an optimization method and proof of optimality are separate matters; a good heuristic layout should not be labeled a proven optimum just because it has a QAP objective.[2][3]

Abstract Reasoning

Begin by typing the two sets and checking equal size or documented dummy padding. Define each feasible bijection \(\pi\) by \(\pi(i)=j\) when item \(i\) occupies position \(j\). In the factorized case evaluate \(\sum_{i,k}F_{ik}D_{\pi(i),\pi(k)}\), with any declared independent-placement term added. In the general case evaluate \(\sum_{i,k}C_{ik,\pi(i),\pi(k)}\). The index convention matters; swapping item and position indices silently can turn a correct model into a different one.[1][3]

Then ask what changes under a swap of two placements. Pair terms involving either swapped item may change, so a locally attractive site for one item can be globally poor. This is the reason the quadratic problem is conceptually different from assigning the cheapest available slot independently. Finally, distinguish the problem from its solution method: Lawler's original paper describes bounds and an exact search framework, but these are reasoning tools for QAP instances, not defining roles of the class.[2]

Knowledge Transfer

The transferable structure is exact: items, positions, bijection, pair coefficients and objective. From plant location one can transfer the idea that a pair's interaction weight is assessed jointly with the two selected positions; in the board setting the interaction is wire connectivity rather than commodity transport. What does not transfer automatically is a transportation metric, a cost magnitude, the best placement, or computational behavior.[1][3]

The factorization \(F_{ik}D_{jl}\) is particularly reusable because it separates “who interacts” from “where the interaction is expensive.” Lawler's broader form shows the limit of that transfer: some joint placement penalties depend on the entire pair of item-site choices and cannot be captured by one shared flow matrix multiplied by one shared distance matrix. Moving between forms therefore requires testing the factorization, not just reusing the label QAP.[2][3]

Examples

Location of economic activities

Koopmans and Beckmann assign indivisible plants to sites. The choice of one plant's location affects transportation involving other plants, because interplant commodity flow is charged according to the assigned site pair. Their original net-revenue objective also permits a plant-site profit term, which is independent of other placements; the pairwise transport part is what makes the assignment quadratic.[1]

Mapped back: items → plants; positions → sites; bijection → permutation matrix with one plant per site; pair-interaction coefficients → flow between two plants times transport cost between their two selected sites; objective → optimize complete placement's net revenue, or minimize the transport part in a cost-only restriction; special factorization → the plant-flow and site-cost matrices.

Backboard wiring

Steinberg's original backboard problem places connected computer components on board positions. Brixius and Anstreicher's later original analysis gives an explicit QAP formulation: their historical instance has 34 components and 36 available slots, so two zero-connection dummy components make a 36-by-36 permutation representation. Pair wire counts combine with a chosen distance between occupied board slots; they examine multiple distance conventions rather than one universal physical “length.”[4][3]

Mapped back: items → electronic components and two declared dummy items in the analyzed instance; positions → 36 board slots; bijection → one item per slot; pair-interaction coefficients → number of wires linking a component pair times the selected slot-pair distance; objective → minimize the declared pairwise wiring surrogate, not every physical routing cost; special factorization → connectivity matrix and board-distance matrix.

Structural Tensions

  • Independent placement simplicity versus interaction fidelity. Linear assignment gives each item-site choice an intelligible standalone score. That loses plant-to-plant transport or component-to-component wiring whose cost depends on both positions. Pair coupling better represents those cases, but sacrifices separability and makes local rankings unreliable. Diagnostic: Does moving another item change the contribution of the focal placement?[1][3]
  • Factorized interpretability versus general expressiveness. The Koopmans–Beckmann product \(F_{ik}D_{jl}\) compactly explains flow and site cost with two matrices, but cannot express every four-way interaction. Lawler's \(C_{ikjl}\) permits broader joint costs, at the price of more coefficient data and less transparent mechanism. Diagnostic: Can the observed pair-placement costs all be represented by a common product \(F_{ik}D_{jl}\)?[2][3]

Structural–Framed Character

  • Evaluative weight: The problem specifies an objective and seeks its optimum, but it does not say which real-world costs are ethically or practically worth minimizing; those values enter as modeled coefficients.
  • Human-practice dependence: Industrial sites and computer boards are application choices, not prerequisites of the formal assignment structure.
  • Institutional origin: Operations research supplied the historical plant-location and circuit-layout lineages; neither institution is constitutive.[1][4]
  • Vocabulary travel: “Assignment” appears in matching and allocation, but only a bijection with pairwise joint-placement objective meets this identity.
  • Import versus recognition: A case is recognized by mapping its feasible permutations and objective coefficients, not by labeling a layout “QAP” or running a familiar solver.

Its character: Near the structural end within mathematics, since the identity is a formal problem schema reusable across industries. It remains domain-specific because permutation feasibility and a quadratic pair-cost objective are constitutive mathematical types, not a cross-domain Prime-level relation of “things affecting each other.”

Structural Core vs. Domain Accent

The core is a constrained bijection whose objective couples two item-position decisions. A portable pattern—interdependent choices invalidate independent local scoring—may merit a future-prime question, but this entry does not claim that Prime identity. The domain accent contains the actual typed sets, binary permutation variables and joint cost tensor. Strip those away and the QAP test disappears.[1][2]

Live Optimization Problem supplies the proposed full genus: QAP has decision variables, feasible alternatives and an objective. Matching and linear assignment are related structures, but neither is asserted as a strict parent based on shared vocabulary. The composed economic or wiring meaning of \(C\) remains an application-specific layer, not part of the universal QAP core.

This entry is a kind of Optimization Problem.

That live genus itself relates to Optimization, but QAP's permutation and interaction-coefficient residual warrants its own node. No canonical edge is added here. Matching (graph theory) is a near neighbor because it selects pairings; it does not inherently include QAP's pair-of-pair cost objective.

Relationships to Other Abstractions

Local relationship map for Quadratic Assignment ProblemParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.QuadraticAssignment ProblemDOMAINDomain-specific abstraction: Optimization Problem — is a kind ofOptimizationProblemDOMAIN

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

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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Linear assignment: Sums independent item-position costs; it can be a relaxation, special degenerate reduction or reformulation ingredient, not a full equivalent of arbitrary QAP.[1][2]
  • Koopmans–Beckmann formulation: The factorized flow-by-position-cost subtype of Lawler's more general four-index formulation.[2][3]
  • Steinberg wiring problem: A concrete backboard setting and benchmark, not the formal identity itself.[4][3]
  • Quadratic bottleneck assignment: Replaces the summed pair objective with a maximum; do not silently alias it.
  • Solver or heuristic: An algorithm may search for a good assignment, while an optimum claim needs its own evidence.[2]

References

[1] Tjalling C. Koopmans and Martin J. Beckmann, “Assignment Problems and the Location of Economic Activities,” original Cowles Foundation Discussion Paper 4 (1955), Yale author-institution scan, §§2 and 6, especially equations 6.2–6.5; revised journal publication Econometrica 25(1):53–76 (1957). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p

[2] Eugene L. Lawler, “The Quadratic Assignment Problem,” Management Science 9(4):586–599 (1963), original publisher page and abstract. The abstract explicitly distinguishes the general formulation from its Koopmans–Beckmann special case and describes constrained linearization and a lower-bound exact method. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p

[3] Nathan W. Brixius and Kurt M. Anstreicher, “The Steinberg Wiring Problem,” original research chapter, author-hosted full paper, §17.1 pp.293–294 and §17.2 pp.294–295. This is later first-hand mathematical work on the Steinberg case, not a claim of direct access to Steinberg's full text. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u

[4] Leon Steinberg, “The Backboard Wiring Problem: A Placement Algorithm,” SIAM Review 3(1):37–50 (1961), original publisher record. The article body was paywalled in this review; the detailed case mapping below is based on Brixius and Anstreicher's original later analysis. registry ↩a ↩b ↩c ↩d