🧩 Constraint Solving POTD:Problem of the Day: Quadratic Assignment Problem (QAP)

[github-actions[bot]]

Problem Statement

The Quadratic Assignment Problem (QAP) asks: given n facilities and n locations, assign each facility to exactly one location (and vice versa) to minimize the total "interaction cost" between all facility pairs.

More formally, let d[i,j] be the distance (or flow) between facilities i and j, and let c[l,m] be the cost to place two locations l and m apart. If we assign facility i to location π(i), the objective is:

minimize Σ_{i,j} d[i,j] · c[π(i), π(j)]

Concrete Instance (4-facilities, 4-locations):

Consider 4 departments in an office:

• Departments: Admin (A), Engineering (E), Sales (S), Operations (O)
• Locations: Floor 1, Floor 2, North Wing, South Wing
• Flow matrix (frequency of inter-department contact):

      A  E  S  O
  A  [0, 1, 8, 0]
  E  [1, 0, 3, 6]
  S  [8, 3, 0, 2]
  O  [0, 6, 2, 0]
  

• Distance matrix (cost to move between locations):

        F1 F2 NW SW
  F1   [0,  2,  5,  7]
  F2   [2,  0,  4,  3]
  NW   [5,  4,  0,  6]
  SW   [7,  3,  6,  0]
  

Objective: Find an assignment that minimizes total interaction cost, accounting for both flow frequency and physical distances. For example, since Admin and Sales have high flow (8), they should be placed close together.

---

Why It Matters

Facility Layout & Factory Design: QAP models the optimal arrangement of production areas in a manufacturing plant. High-volume material flows between departments should minimize transport distance—a classic problem in industrial engineering.

Electronic Circuit Board Design: VLSI designers use QAP to place logical components on a chip to minimize wire lengths; shorter wires reduce latency and power consumption.

Data Center Rack Configuration: Assign servers to racks to minimize network congestion and latency for frequently communicating services.

Organizational Seating: Allocate office spaces so teams that collaborate frequently sit near one another, improving communication and reducing commute time within the building.

---

Modeling Approaches

Approach 1: Quadratic Assignment (Direct)

Paradigm: Mixed-Integer Quadratic Programming (MIQP) or Constraint Programming with quadratic objectives.

Decision variables:

• x[i,l] ∈ {0,1}: binary variable = 1 if facility i is assigned to location l

Constraints:

• Σ_l x[i,l] = 1 for all i (each facility assigned to exactly one location)
• Σ_i x[i,l] = 1 for all l (each location receives exactly one facility)

Objective:

minimize Σ_{i,j,l,m} d[i,j] · c[l,m] · x[i,l] · x[j,m]

Trade-offs:

• Expressiveness: Naturally captures the quadratic nature of the problem.
• Propagation: Quadratic objectives are harder for standard solvers; requires specialized handling (e.g., linearization).
• Scalability: Without linearization, the formulation has O(n4) terms, making it slow for n > 20 unless symmetry-breaking is applied.

Approach 2: Linearization via Auxiliary Variables

Paradigm: Mixed-Integer Linear Programming (MILP).

Decision variables:

• x[i,l] ∈ {0,1}: facility-to-location assignment (as above)
• y[i,j,l,m] ∈ {0,1}: auxiliary variable = 1 if x[i,l] = 1 AND x[j,m] = 1

Constraints:

• Assignment constraints (as above)
• Linearization constraints:
  • y[i,j,l,m] ≤ x[i,l]
  • y[i,j,l,m] ≤ x[j,m]
  • y[i,j,l,m] ≥ x[i,l] + x[j,m] - 1

Objective:

minimize Σ_{i,j,l,m} d[i,j] · c[l,m] · y[i,j,l,m]

Trade-offs:

• Expressiveness: Fully equivalent to the quadratic formulation, but in linear form.
• Propagation: Standard MILP solvers (CPLEX, Gurobi) can apply powerful linear relaxation and cutting planes.
• Scalability: Better for larger instances (n ≤ 100), but the number of auxiliary variables grows O(n4), still challenging.

---

Example Model (OR-Tools / Python)

from ortools.linear_solver import pywraplp

n = 4  # number of facilities/locations
d = [[0, 1, 8, 0],    # flow matrix
     [1, 0, 3, 6],
     [8, 3, 0, 2],
     [0, 6, 2, 0]]
c = [[0, 2, 5, 7],    # distance matrix
     [2, 0, 4, 3],
     [5, 4, 0, 6],
     [7, 3, 6, 0]]

solver = pywraplp.Solver.CreateSolver('SCIP')
if not solver: raise Exception("Solver not available")

# x[i][l] = 1 if facility i goes to location l
x = [[solver.IntVar(0, 1, f'x[{i}][{l}]') for l in range(n)] for i in range(n)]

# Each facility assigned to exactly one location
for i in range(n):
    solver.Add(sum(x[i]) == 1)

# Each location receives exactly one facility
for l in range(n):
    solver.Add(sum(x[i][l] for i in range(n)) == 1)

# Objective: minimize Σ d[i,j] * c[l,m] * x[i,l] * x[j,m]
objective = []
for i in range(n):
    for j in range(n):
        for l in range(n):
            for m in range(n):
                objective.append(d[i][j] * c[l][m] * x[i][l] * x[j][m])
solver.Minimize(sum(objective))

status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print(f"Optimal cost: {solver.ObjectiveValue()}")
    for i in range(n):
        for l in range(n):
            if x[i][l].solution_value() > 0.5:
                print(f"Facility {i} → Location {l}")

---

Key Techniques

1. Linearization & Big-M Constraints

The quadratic terms x[i,l] · x[j,m] are linearized via auxiliary variables and inequalities, enabling the use of powerful MILP solvers. This is essential for handling large QAP instances.

2. Symmetry Breaking

QAP has inherent symmetries (e.g., relabeling locations doesn't change the problem structure). Adding lexicographic ordering constraints on assignment variables can prune large portions of the search space without losing optimal solutions.

3. Bounding via Linear Relaxation

Solve the LP relaxation (allowing fractional x[i,l] values) to obtain a lower bound. Modern solvers use cutting planes and Gomory cuts to tighten this bound, guiding branch-and-bound more efficiently.

4. Specialized Search: Construction + Local Improvement

For large instances (n > 100), exact methods become intractable. Hybrid approaches combine:

• Greedy construction (e.g., nearest-neighbor) to find an initial feasible solution
• Local search (e.g., 2-opt, 3-opt swaps) to iteratively improve the assignment
• Tabu search or simulated annealing to escape local optima

---

Challenge Corner

Can you reduce the size of the model?

The standard linearized QAP has O(n4) auxiliary variables. But many d[i,j] or c[l,m] values may be zero (sparse flow/distance matrices). How would you exploit sparsity to build a smaller formulation? What about symmetries in the matrices—can you merge equivalent variables?

Extension: Suppose facilities have costs that depend on location (e.g., higher rent in premium locations). How would you extend the model to include a linear facility-location cost term, and what solver technique would still apply?

---

References

1. Çela, E. (1998). The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers.

   • Comprehensive treatment of QAP theory, complexity, and algorithmic approaches.

2. Loiola, E. M., de Abreu, N. M. M., et al. (2007). A Survey for the Quadratic Assignment Problem. European Journal of Operational Research, 176(2), 657–690.

   • Thorough review of exact and heuristic methods for QAP.

3. Burkard, R. E., Karisch, S. E., & Rendl, F. (1997). QAPLIB—A Quadratic Assignment Problem Library. Journal of Global Optimization, 10(4), 391–403.

   • Reference to the standard QAP benchmark library ((qaplib.ii.uwr.edu.pl/redacted)

4. Google OR-Tools Solver Documentation: (developers.google.com/redacted)

   • Practical examples of modeling quadratic and mixed-integer programs.

---

Next time on Problem of the Day: Dive into a Satisfiability problem—or a Classic CSP challenge. Share your thoughts on QAP extensions in the comments!

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 10.4 AIC · ⌖ 6.08 AIC · ⊞ 6.5K · ◷

• expires on Oct 29, 2026, 3:37 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #71421.