Quadratic Assignment Problem (QAP) Example

Download Notebook

The Quadratic Assignment Problem (QAP) assigns facilities to locations minimizing total flow-times-distance cost. It is NP-hard and arises in facility layout, keyboard design, and circuit placement.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.quadratic_assignment_problem import (
    QapCollection,
    QapData,
    QapFormulation,
    QapInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 3 facilities and 3 positions with flow and distance matrices.

flow_matrix = np.array(
    [
        [0, 3, 1],
        [3, 0, 4],
        [1, 4, 0],
    ]
)
distance_matrix = np.array(
    [
        [0, 5, 8],
        [5, 0, 3],
        [8, 3, 0],
    ]
)
data = QapData.from_values(
    flow_matrix=flow_matrix,
    distance_matrix=distance_matrix,
    names=["Warehouse", "Factory", "Office"],  # optional
    position_names=["Pos_0", "Pos_1", "Pos_2"],  # optional
)
print(data.to_string())

Quadratic Assignment Data:
  Facilities: 3
  Facility names: ['Warehouse', 'Factory', 'Office']
  Position names: ['Pos_0', 'Pos_1', 'Pos_2']

Plot Data

Visualize facility flows.

data.plot()

(<Axes: title={'center': 'Flow Matrix — 3 facilities'}, xlabel='Facility', ylabel='Facility'>,
 <Axes: title={'center': 'Distance Matrix — 3 positions'}, xlabel='Position', ylabel='Position'>)

Create Formulation

Minimize total cost of flow between facilities weighted by their assigned distances.

formulation = QapFormulation()
print(formulation.to_string(data))

Quadratic Assignment Formulation:
  Facilities: 3
  Positions: 3

Decision Variables:
  x[i,k] in {0,1} for i = 0, ..., 2, k = 0, ..., 2
  x[i,k] = 1 if facility i is assigned to position k
  Total: 9 binary variables

Objective:
  minimize sum_{i,j,k,m} flow[i,j] * distance[k,m] * x[i,k] * x[j,m]

Constraints:
  1. Each facility assigned to exactly one position (3 constraints):
     sum_k x[i,k] == 1  for all i = 0, ..., 2
  2. Each position assigned to exactly one facility (3 constraints):
     sum_i x[i,k] == 1  for all k = 0, ..., 2

Create Instance

Combine data and formulation into a solvable instance.

instance = QapInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Quadratic Assignment Data:
  Facilities: 3
  Facility names: ['Warehouse', 'Factory', 'Office']
  Position names: ['Pos_0', 'Pos_1', 'Pos_2']
Formulation:Quadratic Assignment Formulation:
  Facilities: 3
  Positions: 3

Decision Variables:
  x[i,k] in {0,1} for i = 0, ..., 2, k = 0, ..., 2
  x[i,k] = 1 if facility i is assigned to position k
  Total: 9 binary variables

Objective:
  minimize sum_{i,j,k,m} flow[i,j] * distance[k,m] * x[i,k] * x[j,m]

Constraints:
  1. Each facility assigned to exactly one position (3 constraints):
     sum_k x[i,k] == 1  for all i = 0, ..., 2
  2. Each position assigned to exactly one facility (3 constraints):
     sum_i x[i,k] == 1  for all k = 0, ..., 2

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Quadratic Assignment Solution:
  Assignment: {'Warehouse': 'Pos_0', 'Factory': 'Pos_1', 'Office': 'Pos_2'}
  Total cost: 70.0
  Valid: True

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'QAP Solution — total cost: 70.00'}, xlabel='Position', ylabel='Facility'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = QapCollection.from_random(min_size=3, max_size=5, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: quadratic_assignment_problem<quadratic_assignment_problem>
Minimize
  32.5 * x_Facility_0_Position_0 * x_Facility_1_Position_1
  + 22.5 * x_Facility_0_Position_0 * x_Facility_1_Position_2
  + 32.5 * x_Facility_0_Position_0 * x_Facility_2_Position_1
  + 22.5 * x_Facility_0_Position_0 * x_Facility_2_Position_2
  + 32.5 * x_Facility_0_Position_1 * x_Facility_1_Position_0
  + 25 * x_Facility_0_Position_1 * x_Facility_1_Position_2
  + 32.5 * x_Facility_0_Position_1 * x_Facility_2_Position_0
  + 25 * x_Facility_0_Position_1 * x_Facility_2_Position_2
  + 22.5 * x_Facility_0_Position_2 * x_Facility_1_Position_0
  + 25 * x_Facility_0_Position_2 * x_Facility_1_Position_1
  + 22.5 * x_Facility_0_Position_2 * x_Facility_2_Position_0
  + 25 * x_Facility_0_Position_2 * x_Facility_2_Position_1
  + 52 * x_Facility_1_Position_0 * x_Facility_2_Position_1
  + 36 * x_Facility_1_Position_0 * x_Facility_2_Position_2
  + 52 * x_Facility_1_Position_1 * x_Facility_2_Position_0
  + 40 * x_Facility_1_Position_1 * x_Facility_2_Position_2
  + 36 * x_Facility_1_Position_2 * x_Facility_2_Position_0
  + 40 * x_Facility_1_Position_2 * x_Facility_2_Position_1
Subject To
  facility_Facility_0: x_Facility_0_Position_0 + x_Facility_0_Position_1
    + x_Facility_0_Position_2 == 1
  facility_Facility_1: x_Facility_1_Position_0 + x_Facility_1_Position_1
    + x_Facility_1_Position_2 == 1
  facility_Facility_2: x_Facility_2_Position_0 + x_Facility_2_Position_1
    + x_Facility_2_Position_2 == 1
  position_Position_0: x_Facility_0_Position_0 + x_Facility_1_Position_0
    + x_Facility_2_Position_0 == 1
  position_Position_1: x_Facility_0_Position_1 + x_Facility_1_Position_1
    + x_Facility_2_Position_1 == 1
  position_Position_2: x_Facility_0_Position_2 + x_Facility_1_Position_2
    + x_Facility_2_Position_2 == 1
Binary
  x_Facility_0_Position_0 x_Facility_0_Position_1 x_Facility_0_Position_2
  x_Facility_1_Position_0 x_Facility_1_Position_1 x_Facility_1_Position_2
  x_Facility_2_Position_0 x_Facility_2_Position_1 x_Facility_2_Position_2