Motivation
Classical combinatorial optimization problem with applications in facility layout, VLSI design, and keyboard arrangement; generalizes TSP and has a direct QUBO formulation (Lucas 2014, §8).
Definition
Name: QuadraticAssignment
Reference: : Garey & Johnson, ND43; Koopmans & Beckmann (1957); Burkard, Çela, Pardalos & Pitsoulis (1998) survey
Given $n$ facilities and $n$ locations, a flow matrix $F \in \mathbb{R}^{n \times n}$ where $F_{ij}$ is the flow between facilities $i$ and $j$, and a distance matrix $D \in \mathbb{R}^{n \times n}$ where $D_{kl}$ is the distance between locations $k$ and $l$, find a permutation $\pi : {0,\ldots,n-1} \to {0,\ldots,n-1}$ that minimizes
$$\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} F_{ij} \cdot D_{\pi(i)\pi(j)}$$
Variables
-
Count: $n^2$ (one binary variable per facility-location pair)
-
Per-variable domain: binary ${0, 1}$
-
Meaning: $x_{ij} = 1$ if facility $i$ is assigned to location $j$; the configuration must be a permutation matrix: $\sum_{j} x_{ij} = 1$ for all $i$ and $\sum_{i} x_{ij} = 1$ for all $j$
Schema (data type)
Type name: QuadraticAssignment
Variants: weight type ($W =$ i32 or f64); no graph topology variant (matrix input)
| Field |
Type |
Description |
| size |
usize |
number of facilities/locations $n$
|
| flow |
Vec<W> |
$n \times n$ flow matrix $F$ in row-major order; $F_{ij}$ = flow between facilities $i$ and $j$
|
| distance |
Vec<W> |
$n \times n$ distance matrix $D$ in row-major order; $D_{kl}$ = distance between locations $k$ and $l$
|
Complexity
-
Best known exact algorithm: $O(n! \cdot n^2)$ brute-force over all $n!$ permutations (each evaluated in $O(n^2)$); no sub-exponential exact algorithm is known for the general case. All practical exact methods (branch-and-bound with Gilmore-Lawler bounds, Lawler 1963) improve average-case but not worst-case complexity.
-
References: Lawler (1963), Management Science; Burkard, Çela, Pardalos & Pitsoulis (1998) survey
Extra Remark
QAP was introduced by Koopmans & Beckmann (1957) to model the assignment of economic activities to locations. It generalizes TSP: setting $F$ to the cycle adjacency matrix and $D$ to pairwise distances between cities recovers TSP exactly. QAP is NP-hard and not approximable to any constant factor unless P=NP (Sahni & Gonzalez 1976). Despite its simple formulation, QAP is considered one of the hardest NP-hard problems in practice; benchmark instances with $n > 30$ often remain unsolved exactly (see QAPLIB).
How to solve
Example Instance
Instance 1: $n = 3$ (exhaustive enumeration)
Flow matrix $F$ (flow between facilities $i$ and $j$):
| $F$ |
fac 0 |
fac 1 |
fac 2 |
| fac 0 |
0 |
5 |
2 |
| fac 1 |
5 |
0 |
3 |
| fac 2 |
2 |
3 |
0 |
Distance matrix $D$ (distance between locations $k$ and $l$):
| $D$ |
loc 0 |
loc 1 |
loc 2 |
| loc 0 |
0 |
8 |
4 |
| loc 1 |
8 |
0 |
6 |
| loc 2 |
4 |
6 |
0 |
All $3! = 6$ permutations and their costs:
| Permutation $(\pi(0),, \pi(1),, \pi(2))$
|
Cost |
| (0, 1, 2) |
132 |
| (0, 2, 1) |
108 ← optimal |
| (1, 0, 2) |
128 |
| (1, 2, 0) |
116 |
| (2, 0, 1) |
112 |
| (2, 1, 0) |
124 |
Optimal: $\pi = (0, 2, 1)$ — facility 0 → location 0, facility 1 → location 2, facility 2 → location 1 — with cost 108.
Verification for $\pi = (0, 2, 1)$, i.e., $\pi(0)=0,, \pi(1)=2,, \pi(2)=1$ (diagonal terms $F_{ii}=D_{ii}=0$ vanish):
$$\text{cost} = F_{01}D_{\pi(0)\pi(1)} + F_{02}D_{\pi(0)\pi(2)} + F_{10}D_{\pi(1)\pi(0)} + F_{12}D_{\pi(1)\pi(2)} + F_{20}D_{\pi(2)\pi(0)} + F_{21}D_{\pi(2)\pi(1)}$$
$$= F_{01}D_{02} + F_{02}D_{01} + F_{10}D_{20} + F_{12}D_{21} + F_{20}D_{10} + F_{21}D_{12}$$
$$= 5 \cdot 4 + 2 \cdot 8 + 5 \cdot 4 + 3 \cdot 6 + 2 \cdot 8 + 3 \cdot 6 = 20 + 16 + 20 + 18 + 16 + 18 = 108$$
Instance 2: $n = 4$ (exhaustive enumeration)
4 facilities and 4 locations arranged on a straight line; $D_{kl} = |k - l|$.
Flow matrix $F$:
| $F$ |
fac 0 |
fac 1 |
fac 2 |
fac 3 |
| fac 0 |
0 |
3 |
1 |
2 |
| fac 1 |
3 |
0 |
4 |
1 |
| fac 2 |
1 |
4 |
0 |
2 |
| fac 3 |
2 |
1 |
2 |
0 |
Distance matrix $D$ ($D_{kl} = |k - l|$, line topology):
| $D$ |
loc 0 |
loc 1 |
loc 2 |
loc 3 |
| loc 0 |
0 |
1 |
2 |
3 |
| loc 1 |
1 |
0 |
1 |
2 |
| loc 2 |
2 |
1 |
0 |
1 |
| loc 3 |
3 |
2 |
1 |
0 |
All $4! = 24$ permutations and their costs:
| Permutation $(\pi(0),, \pi(1),, \pi(2),, \pi(3))$
|
Cost |
| (0, 1, 2, 3) |
38 ← optimal |
| (0, 1, 3, 2) |
42 |
| (0, 2, 1, 3) |
44 |
| (0, 2, 3, 1) |
40 |
| (0, 3, 1, 2) |
50 |
| (0, 3, 2, 1) |
42 |
| (1, 0, 2, 3) |
42 |
| (1, 0, 3, 2) |
46 |
| (1, 2, 0, 3) |
46 |
| (1, 2, 3, 0) |
38 ← optimal |
| (1, 3, 0, 2) |
52 |
| (1, 3, 2, 0) |
40 |
| (2, 0, 1, 3) |
40 |
| (2, 0, 3, 1) |
52 |
| (2, 1, 0, 3) |
38 ← optimal |
| (2, 1, 3, 0) |
46 |
| (2, 3, 0, 1) |
46 |
| (2, 3, 1, 0) |
42 |
| (3, 0, 1, 2) |
42 |
| (3, 0, 2, 1) |
50 |
| (3, 1, 0, 2) |
40 |
| (3, 1, 2, 0) |
44 |
| (3, 2, 0, 1) |
42 |
| (3, 2, 1, 0) |
38 ← optimal |
Optimal cost: 38, achieved by 4 permutations: $(0,1,2,3)$, $(1,2,3,0)$, $(2,1,0,3)$, $(3,2,1,0)$.
Verification for $\pi = (0, 1, 2, 3)$ (identity assignment). Since $F$ is symmetric, pairs $(i,j)$ and $(j,i)$ contribute equally:
$$\text{cost} = 2\sum_{i < j} F_{ij}, D_{\pi(i)\pi(j)} = 2,(F_{01}D_{01} + F_{02}D_{02} + F_{03}D_{03} + F_{12}D_{12} + F_{13}D_{13} + F_{23}D_{23})$$
$$= 2,(3{\cdot}1 + 1{\cdot}2 + 2{\cdot}3 + 4{\cdot}1 + 1{\cdot}2 + 2{\cdot}1) = 2,(3+2+6+4+2+2) = 2 \times 19 = 38$$
The 4-fold degeneracy arises from the line's reflection symmetry: reversing all location indices ($\pi(i) \mapsto 3 - \pi(i)$) leaves every distance $D_{kl} = |k-l|$ unchanged, so any optimal permutation pairs with its mirror image.
Motivation
Classical combinatorial optimization problem with applications in facility layout, VLSI design, and keyboard arrangement; generalizes TSP and has a direct QUBO formulation (Lucas 2014, §8).
Definition
Name: QuadraticAssignment
Reference: : Garey & Johnson, ND43; Koopmans & Beckmann (1957); Burkard, Çela, Pardalos & Pitsoulis (1998) survey
Given$n$ facilities and $n$ locations, a flow matrix $F \in \mathbb{R}^{n \times n}$ where $F_{ij}$ is the flow between facilities $i$ and $j$ , and a distance matrix $D \in \mathbb{R}^{n \times n}$ where $D_{kl}$ is the distance between locations $k$ and $l$ , find a permutation $\pi : {0,\ldots,n-1} \to {0,\ldots,n-1}$ that minimizes
Variables
Schema (data type)
Type name: QuadraticAssignment$W =$
Variants: weight type (
i32orf64); no graph topology variant (matrix input)Complexity
Extra Remark
QAP was introduced by Koopmans & Beckmann (1957) to model the assignment of economic activities to locations. It generalizes TSP: setting$F$ to the cycle adjacency matrix and $D$ to pairwise distances between cities recovers TSP exactly. QAP is NP-hard and not approximable to any constant factor unless P=NP (Sahni & Gonzalez 1976). Despite its simple formulation, QAP is considered one of the hardest NP-hard problems in practice; benchmark instances with $n > 30$ often remain unsolved exactly (see QAPLIB).
How to solve
Example Instance
Instance 1:$n = 3$ (exhaustive enumeration)
Flow matrix$F$ (flow between facilities $i$ and $j$ ):
Distance matrix$D$ (distance between locations $k$ and $l$ ):
All$3! = 6$ permutations and their costs:
Optimal:$\pi = (0, 2, 1)$ — facility 0 → location 0, facility 1 → location 2, facility 2 → location 1 — with cost 108.
Verification for$\pi = (0, 2, 1)$ , i.e., $\pi(0)=0,, \pi(1)=2,, \pi(2)=1$ (diagonal terms $F_{ii}=D_{ii}=0$ vanish):
Instance 2:$n = 4$ (exhaustive enumeration)
4 facilities and 4 locations arranged on a straight line;$D_{kl} = |k - l|$ .
Flow matrix$F$ :
Distance matrix$D$ ($D_{kl} = |k - l|$ , line topology):
All$4! = 24$ permutations and their costs:
Optimal cost: 38, achieved by 4 permutations:$(0,1,2,3)$ , $(1,2,3,0)$ , $(2,1,0,3)$ , $(3,2,1,0)$ .
Verification for$\pi = (0, 1, 2, 3)$ (identity assignment). Since $F$ is symmetric, pairs $(i,j)$ and $(j,i)$ contribute equally:
The 4-fold degeneracy arises from the line's reflection symmetry: reversing all location indices ($\pi(i) \mapsto 3 - \pi(i)$) leaves every distance$D_{kl} = |k-l|$ unchanged, so any optimal permutation pairs with its mirror image.