Skip to content

Quadratic Assignment API Reference

Data

Data model for Quadratic Assignment use case.

QapData

Bases: UcData

Data for the Quadratic Assignment Problem (QAP).

Assigns n facilities to n positions to minimize the total cost, which is the sum of flow * distance for all facility pairs.

Attributes:

Name Type Description
name Literal['quadratic_assignment_problem']

Identifier for this data type.
flow_matrix NumPyArray

An n x n matrix of flows between facilities.
distance_matrix NumPyArray

An n x n matrix of distances between positions.
names list[str]

Identifiers for each facility. Defaults to Facility 0, ..., Facility n-1.
position_names list[str]

Identifiers for each position. Defaults to Position 0, ..., Position n-1.

plot(*, ax: Axes | None = None) -> Axes | tuple[Axes, Axes]

Plot the flow and distance matrices side by side.

Parameters:

Name Type Description Default
ax Axes | None

Matplotlib axes to draw on. If None, a new figure with two subplots is created.

 None

Returns:

Type Description
Axes | tuple[Axes, Axes]

A single axes when ax is provided, otherwise a tuple of (flow_ax, distance_ax).

to_string() -> str

Return a string describing the data.

Returns:

Type Description
str

String representation of the data.

from_values(flow_matrix: np.ndarray | list[list[float]], distance_matrix: np.ndarray | list[list[float]], names: list[str] | None = None, position_names: list[str] | None = None) -> QapData staticmethod

Create a QapData instance from flow and distance matrices.

Parameters:

Name Type Description Default
flow_matrix ndarray | list[list[float]]

An n x n symmetric matrix of flows between facilities.

 required
distance_matrix ndarray | list[list[float]]

An n x n symmetric matrix of distances between positions.

 required
names list[str] | None

Identifiers for each facility. Defaults to Facility 0, ..., Facility n-1.

 None
position_names list[str] | None

Identifiers for each position. Defaults to Position 0, ..., Position n-1.

 None

Returns:

Type Description
QapData

A QapData instance with the given matrices.

generate_random(n: int = 4, seed: int | None = None) -> QapData staticmethod

Generate a random Quadratic Assignment instance.

Creates symmetric flow and distance matrices.

Parameters:

Name Type Description Default
n int

Number of facilities/positions, by default 4.

 4
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
QapData

A randomly generated data instance.

Formulation

Formulation for Quadratic Assignment use case.

QapFormulation

Bases: UcFormulation[QapData, QapSolution]

Constraint-based formulation for Quadratic Assignment.

Mathematical Formulation 
Decision Variables:
    x_{i,k} in {0,1}: 1 if facility i is assigned to position k

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

Constraints:
    1. Each facility one position: sum_k x[i,k] == 1 for all i
    2. Each position one facility: sum_i x[i,k] == 1 for all k

to_string(data: QapData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Name Type Description Default
data QapData

The problem data.

 required

Returns:

Type Description
str

String representation of the formulation.

formulate(data: QapData) -> Model staticmethod

Formulate the Quadratic Assignment Problem.

Parameters:

Name Type Description Default
data QapData

The problem data.

 required

Returns:

Type Description
Model

A LunaModel ready to be solved.

interpret(solution: Solution, data: QapData) -> QapSolution staticmethod

Extract solution from quantum result.

Parameters:

Name Type Description Default
solution Solution

The quantum solution.

 required
data QapData

The problem data.

 required

Returns:

Type Description
QapSolution

Structured solution with metrics.

Solution

Solution model for Quadratic Assignment use case.

QapSolution

Bases: UcSolution

Solution for the Quadratic Assignment Problem.

Attributes:

Name Type Description
name Literal['quadratic_assignment_problem']

Identifier for this solution type.
assignment dict[str, str]

Mapping from facility name to position name.
total_cost float

Total flow * distance cost of the assignment.
is_valid bool

Whether the assignment is a valid permutation.

plot(data: QapData | None = None, *, ax: Axes | None = None) -> Axes

Plot the assignment result as an item-position matrix.

Parameters:

Name Type Description Default
data QuadraticAssignmentData | None

Problem data for context.

 None
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

to_string() -> str

Return a string describing the solution.

Returns:

Type Description
str

String representation of the solution.

Instance

Instance model for QuadraticAssignment use case.

QapInstance

Bases: UcInstance[QapData, QapFormulation, QapSolution]

Instance combining data and formulation for QuadraticAssignment.

Collection

Collection of Quadratic Assignment instances.

QapCollection

Bases: UcInstanceCollection[QapInstance]

Collection of Quadratic Assignment instances.

from_random(min_size: int | None = None, max_size: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> QapCollection classmethod

Generate random Quadratic Assignment instances.

Parameters:

Name Type Description Default
min_size int | None

Minimum number of facilities/locations.

 None
max_size int | None

Maximum number of facilities/locations.

 None
num_instances int

Number of instances per size, by default 1.

 1
seed int | None

Random seed for reproducibility, by default None.

 None
sizes Sequence[int] | None

Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_size/max_size, by default None.

 None

Returns:

Type Description
QapCollection

Collection containing generated instances.

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

Name Type Description Default
max_runtime float

SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

 3600
quiet bool

Suppress the SCIP solver output.

 True

Returns:

Type Description
list[bool]

Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises:

Type Description
ValueError

If max_runtime is not positive.