[Model] QuadraticAssignmentProblem

[zazabap]

Motivation

One of the hardest NP-hard combinatorial optimization problems; has natural reductions to QUBO and ILP. Widely used in VLSI layout, facility planning, and logistics.

Definition

Name: QuadraticAssignmentProblem
Reference: Koopmans & Beckmann, 1957; Sahni & Gonzalez, 1976

Given $n$ facilities, $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$ minimizing:

$$\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 $x_{ik}$ per facility-location pair)
• Per-variable domain: binary ${0, 1}$
• Meaning: $x_{ik} = 1$ if facility $i$ is assigned to location $k$. Permutation constraints: $\sum_k x_{ik} = 1$ for all $i$, $\sum_i x_{ik} = 1$ for all $k$.

Schema (data type)

Type name: QuadraticAssignmentProblem
Variants: symmetric ($F$ and $D$ both symmetric), asymmetric

Field	Type	Description
flow	Vec<Vec<f64>>	Flow matrix $F$: $f_{ij}$ = flow between facilities $i$ and $j$
distance	Vec<Vec<f64>>	Distance matrix $D$: $d_{kl}$ = distance between locations $k$ and $l$

Problem Size

Metric	Expression	Description
num_facilities	$n$	Number of facilities (and locations)

Complexity

• Decision complexity: NP-hard; NP-hard to approximate within any constant factor (Sahni & Gonzalez, 1976)
• Best known exact algorithm: $O(2^n \cdot n)$ via dynamic programming; practically solved up to $n \approx 30$ with branch-and-bound
• References: Sahni & Gonzalez 1976; QAPLIB benchmark library

Extra Remark

QAP generalizes TSP (set $F$ to a cycle adjacency matrix) and graph isomorphism (set both $F$ and $D$ to adjacency matrices). The QUBO formulation expands the quadratic objective with permutation penalty terms, making it a natural candidate for quantum annealing.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new QAP → ILP rule issue (to be filed).

Bruteforce: enumerate all $n!$ permutations $\pi$, compute $\sum_{i,j} f_{ij} \cdot d_{\pi(i),\pi(j)}$, return minimum.

Example Instance

$n = 4$ facilities and locations.

Flow matrix $F$ (flow between facilities):

$F$	0	1	2	3
0	0	3	7	2
1	3	0	1	5
2	7	1	0	4
3	2	5	4	0

Distance matrix $D$ (distance between locations):

$D$	0	1	2	3
0	0	1	2	5
1	1	0	4	3
2	2	4	0	1
3	5	3	1	0

Optimal permutation: $\pi = (1, 3, 0, 2)$, cost $= 84$.

Facility pair	Flow	Assigned locations	Distance	Contribution
$(0, 2)$	7	$(1, 0)$	1	$2 \times 7 \times 1 = 14$
$(1, 3)$	5	$(3, 2)$	1	$2 \times 5 \times 1 = 10$
$(2, 3)$	4	$(0, 2)$	2	$2 \times 4 \times 2 = 16$
$(0, 1)$	3	$(1, 3)$	3	$2 \times 3 \times 3 = 18$
$(0, 3)$	2	$(1, 2)$	4	$2 \times 2 \times 4 = 16$
$(1, 2)$	1	$(3, 0)$	5	$2 \times 1 \times 5 = 10$

The two highest-flow pairs (flow 7 and 5) are each assigned distance 1, while the lowest-flow pair (flow 1) absorbs the largest distance 5.

Compare: identity $\pi = (0,1,2,3)$ costs 100; worst assignment costs 152.

[zazabap]

Withdrawing this issue — the QAP formulation is too complex for a clean contribution to this project.