[Model] QuadraticAssignment

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] QuadraticAssignment"
labels: model
assignees: ''

Motivation

QUADRATIC ASSIGNMENT PROBLEM (P119) from Garey & Johnson, A2 ND43. A classical NP-hard combinatorial optimization problem first introduced by Koopmans and Beckmann (1957) for facility location. It models the problem of assigning facilities to locations while minimizing the total interaction cost (product of flows between facilities and distances between their assigned locations). QAP is considered one of the "hardest of the hard" combinatorial optimization problems, with even moderate-size instances (n > 20) being beyond exact solvers.

Associated reduction rules:

• As source: None found in current rule set.
• As target: R64 (HAMILTONIAN CIRCUIT to QUADRATIC ASSIGNMENT PROBLEM)

Definition

Name: QuadraticAssignment
Canonical name: Quadratic Assignment Problem (QAP)
Reference: Garey & Johnson, Computers and Intractability, A2 ND43

Mathematical definition:

INSTANCE: Non-negative integer costs c_{ij}, 1 <= i,j <= n, and distances d_{kl}, 1 <= k,l <= m.
QUESTION (optimization): Find a one-to-one function f: {1,2,...,n} -> {1,2,...,m} minimizing
sum_{i=1}^{n} sum_{j=1, j!=i}^{n} c_{ij} * d_{f(i)f(j)}.

Variables

• Count: n * m binary variables x_{ik}, representing assignment of facility i to location k. This is equivalent to choosing an injection from n facilities to m locations (typically n = m, giving a permutation).
• Per-variable domain: {0, 1} — x_{ik} = 1 if facility i is assigned to location k, 0 otherwise.
• Meaning: The dims() method returns [m; n], where variable i ranges over {0, 1, ..., m-1} indicating the location assigned to facility i. The evaluate() method checks injectivity (no two facilities share a location) and returns SolutionSize::Invalid for non-injective assignments. For valid assignments, the total cost is sum over all facility pairs (i,j) of flow c_{ij} times distance d_{f(i),f(j)}, returned as SolutionSize::Valid(cost) with Direction::Minimize.

Schema (data type)

Type name: QuadraticAssignment
Variants: none (algebraic problem, no graph type parameter)
Category: src/models/algebraic/ (matrix-based input, alongside QUBO and ILP)

Field	Type	Description
cost_matrix	Vec<Vec<i64>>	n x n flow/cost matrix C, where c_{ij} = interaction between facilities i and j
distance_matrix	Vec<Vec<i64>>	m x m distance matrix D, where d_{kl} = distance between locations k and l

Notes:

• This is an optimization problem: Metric = SolutionSize<i64>, implementing OptimizationProblem with Direction::Minimize.
• Typically n = m (same number of facilities and locations), giving a bijection.
• Key getter methods: num_facilities() (= n), num_locations() (= m).
• The evaluate() method must check injectivity of the assignment and return SolutionSize::Invalid for configurations where two facilities are assigned the same location.
• Special case: if d_{kl} = |k - l| and C is a 0-1 symmetric matrix, this becomes OPTIMAL LINEAR ARRANGEMENT (also NP-complete).

Complexity

• Decision complexity: Strongly NP-hard (Sahni and Gonzalez, 1976; transformation from HAMILTONIAN CIRCUIT).
• Inapproximability: For arbitrary epsilon > 0, no polynomial-time epsilon-approximation algorithm exists unless P = NP (Sahni and Gonzalez, 1976).
• Best known exact algorithm: Branch-and-bound algorithms. The brute force approach enumerates all n! permutations in O(n! * n^2) time. Advanced branch-and-bound methods (e.g., Anstreicher 2003, using convex quadratic bounds) can solve instances of size up to about n = 30 in practice, but worst case remains factorial.
• Complexity string: "factorial(num_facilities)" — brute-force search space is n! permutations.
• Practical limits: Exact solutions are feasible only for n <= 30 with state-of-the-art branch-and-bound. Instances from the QAPLIB benchmark library with n >= 20 can take hours to days.
• References:
  • S. Sahni and T. Gonzalez (1976). "P-complete approximation problems." Journal of the ACM, 23(3):555-565. NP-hardness and inapproximability.
  • T.C. Koopmans and M. Beckmann (1957). "Assignment problems and the location of economic activities." Econometrica, 25(1):53-76. Original QAP formulation.
  • K.M. Anstreicher (2003). "Recent advances in the solution of quadratic assignment problems." Mathematical Programming Ser. B, 97:27-42.

Extra Remark

Full book text:

INSTANCE: Non-negative integer costs c_{ij}, 1 <= i,j <= n, and distances d_{kl}, 1 <= k,l <= m, bound B in Z^+.
QUESTION: Is there a one-to-one function f: {1,2,...,n} -> {1,2,...,m} such that
sum_{i=1}^{n} sum_{j=1, j!=i}^{n} c_{ij} d_{f(i)f(j)} <= B ?
Reference: [Sahni and Gonzalez, 1976]. Transformation from HAMILTONIAN CIRCUIT.
Comment: Special case in which each d_{kl} = k - l and all c_{ji} = c_{ij} in {0,1} is the NP-complete OPTIMAL LINEAR ARRANGEMENT problem. The general problem is discussed, for example, in [Garfinkel and Nemhauser, 1972].

How to solve

• It can be solved by (existing) bruteforce. Enumerate all n! permutations f and compute the objective sum_{i,j} c_{ij} * d_{f(i)f(j)} for each; return the one with minimum cost. Time: O(n! * n^2).
• It can be solved by reducing to integer programming. Linearize the quadratic objective using binary assignment variables x_{ik} (facility i to location k) and auxiliary variables for products x_{ik} * x_{jl}. Standard Koopmans-Beckmann linearization.
• Other: Branch-and-bound with Gilmore-Lawler lower bounds; semidefinite relaxation bounds; metaheuristics (simulated annealing, genetic algorithms, ant colony optimization) for approximate solutions.

Example Instance

Instance (n = m = 4):

Cost matrix C (flows between 4 facilities):

     1  2  3  4
1  [ 0  5  2  0 ]
2  [ 5  0  0  3 ]
3  [ 2  0  0  4 ]
4  [ 0  3  4  0 ]

Distance matrix D (distances between 4 locations):

     1  2  3  4
1  [ 0  4  1  1 ]
2  [ 4  0  3  4 ]
3  [ 1  3  0  4 ]
4  [ 1  4  4  0 ]

High-flow pairs: F1-F2 (flow 5), F3-F4 (flow 4), F2-F4 (flow 3), F1-F3 (flow 2). Short-distance pairs: L1-L3 (dist 1), L1-L4 (dist 1), L2-L3 (dist 3).

Evaluation of assignment f = (1,2,3,4) (identity):
Cost = 5*4 + 2*1 + 0*1 + 5*4 + 0*3 + 3*4 + 2*1 + 0*3 + 4*4 + 0*1 + 3*4 + 4*4 = 20 + 2 + 0 + 20 + 0 + 12 + 2 + 0 + 16 + 0 + 12 + 16 = 100

Evaluation of assignment f = (4,1,2,3) (optimal):
F1→L4, F2→L1, F3→L2, F4→L3. Places the highest-flow pair F1-F2 (flow 5) at locations L4-L1 (distance 1), and pair F3-F4 (flow 4) at L2-L3 (distance 3).
Cost = 5*1 + 2*4 + 0*4 + 5*1 + 0*4 + 3*1 + 2*4 + 0*4 + 4*3 + 0*4 + 3*1 + 4*3 = 5 + 8 + 0 + 5 + 0 + 3 + 8 + 0 + 12 + 0 + 3 + 12 = 56

Optimal solution: f* = (4,1,2,3) with cost 56 (unique optimum). The key insight is that the highest-flow pair F1-F2 (flow 5) is placed at adjacent locations L4-L1 (distance 1), saving 5*(4-1)=15 compared to the identity assignment.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; classical NP-hard with known reduction from Hamiltonian Circuit
Non-trivial	✅ Pass	Distinct from all existing problems (QAP involves permutation/injection variables + bilinear cost, unlike QUBO's binary variables or ILP's linear constraints)
Correctness	⚠️ Warn	All references verified, but complexity string "num_facilities!" uses factorial — not supported by the Expr parser
Well-written	⚠️ Warn	Dual optimization/satisfaction framing is ambiguous; naming convention question; complexity string not implementable

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

QuadraticAssignment does not exist in the codebase (confirmed via pred show). The problem is a classical NP-hard combinatorial optimization problem (Garey & Johnson A2 ND43) with practical applications in facility location. It has a known reduction from Hamiltonian Circuit, which would connect it to the existing reduction graph. Pass.

Non-trivial

QAP is genuinely distinct from all 24 existing problems:

• Unlike QUBO (binary variables, quadratic objective over {0,1}^n), QAP operates on permutations/injections with a bilinear cost structure c_{ij} * d_{f(i)f(j)}.
• Unlike ILP (linear constraints, linear/integer objective), QAP's objective is inherently quadratic in the assignment.
• Unlike TravelingSalesman (single tour minimization over distances), QAP considers pairwise facility-flow interactions.
• The feasibility constraint (injective function) and objective structure are not captured by any existing model. Pass.

Correctness

Reference verification:

• Sahni and Gonzalez (1976) — "P-Complete Approximation Problems," JACM 23(3):555-565. ✅ Verified on ACM DL and Semantic Scholar. Correctly cited for NP-hardness and inapproximability of QAP.
• Koopmans and Beckmann (1957) — "Assignment Problems and the Location of Economic Activities," Econometrica 25(1):53-76. ✅ Verified on Econometric Society and JSTOR. Correctly cited as the original QAP formulation.
• Anstreicher (2003) — "Recent advances in the solution of quadratic assignment problems," Mathematical Programming Ser. B 97:27-42. ✅ Verified on SpringerLink. Correctly cited for branch-and-bound advances.

Complexity string concern: The proposed complexity string "num_facilities!" uses factorial notation. However, the project's Expr AST (in src/expr.rs) only supports: constants, variables, +, -, *, /, ^, exp(), log(), sqrt(). There is no factorial operator. This would need to be approximated, e.g., using Stirling's approximation sqrt(2 * 3.14159 * num_facilities) * (num_facilities / 2.71828)^num_facilities or represented differently. This is not a correctness failure per se — the factorial bound is accurate for brute force — but it cannot be expressed in the current system.

Example verification: The worked example calculations for assignments f=(1,2,3,4) and f=(2,1,4,3) both yielding cost 38 are arithmetically correct (manually verified).

Well-written

The issue is generally well-structured and covers all required sections. Specific concerns:

1. Optimization vs. Satisfaction ambiguity: The issue describes both a satisfaction version (is cost ≤ B?) and an optimization version (minimize total cost), stating the schema should support both. In this codebase, a problem implements either OptimizationProblem (with Metric = SolutionSize<T>) or SatisfactionProblem (with Metric = bool), not both simultaneously. The issue should pick one formulation. For consistency with existing problems (QUBO, MaxCut, etc.), the optimization version (minimize) is more natural.

2. Naming convention: The project uses explicit optimization prefixes (Maximum..., Minimum...) for optimization problems. If this is a minimization problem, it might need to be MinimumQuadraticAssignment. However, other problems without explicit direction exist (e.g., QUBO, MaxCut), so QuadraticAssignment may be acceptable — but this should be a deliberate choice.

3. Complexity string not implementable: As noted above, "num_facilities!" cannot be parsed by the Expr system. The issue should propose an alternative representation.

4. Variable encoding: The issue proposes per-variable domain {0, 1, ..., m-1}, meaning dims() would return [m; n]. However, this does not enforce injectivity — evaluate() would need to check for duplicate assignments and return Invalid. This is workable but should be stated explicitly.

5. Example quality: The n=4 example is adequate, but the issue notes that the "optimal assignment requires checking all 4! = 24 permutations" without actually stating the optimal solution. For completeness, the optimal assignment and its cost should be provided.

Recommendations

• Pick one formulation (optimization preferred) and remove the dual-version ambiguity from the schema. The bound field can be omitted for the optimization version.
• Provide the optimal solution for the n=4 example instance (enumerate all 24 permutations or state which one is optimal).
• Replace the complexity string with an Expr-compatible expression, or note that an approximation (e.g., Stirling's) will be used during implementation.
• Clarify the category: Based on the input structure (two matrices), this would likely go in src/models/algebraic/ alongside QUBO and ILP.