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 (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:

  • ax (Axes | None, default: None ) –

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

Returns:

  • 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:

  • 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:

  • flow_matrix (ndarray | list[list[float]]) –

    An n x n symmetric matrix of flows between facilities.

  • distance_matrix (ndarray | list[list[float]]) –

    An n x n symmetric matrix of distances between positions.

  • names (list[str] | None, default: None ) –

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

  • position_names (list[str] | None, default: None ) –

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

Returns:

  • 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:

  • n (int, default: 4 ) –

    Number of facilities/positions, by default 4.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

  • 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:

  • data (QapData) –

    The problem data.

Returns:

  • str –

    String representation of the formulation.

formulate(data: QapData) -> Model staticmethod

Formulate the Quadratic Assignment Problem.

Parameters:

  • data (QapData) –

    The problem data.

Returns:

  • Model –

    A LunaModel ready to be solved.

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

Extract solution from quantum result.

Parameters:

  • solution (Solution) –

    The quantum solution.

  • data (QapData) –

    The problem data.

Returns:

Solution

Solution model for Quadratic Assignment use case.

QapSolution

Bases: UcSolution

Solution for the Quadratic Assignment Problem.

Attributes:

  • 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:

  • data (QuadraticAssignmentData | None, default: None ) –

    Problem data for context.

  • ax (Axes | None, default: None ) –

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

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the solution.

Returns:

  • 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:

  • min_size (int | None, default: None ) –

    Minimum number of facilities/locations.

  • max_size (int | None, default: None ) –

    Maximum number of facilities/locations.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

  • sizes (Sequence[int] | None, default: None ) –

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

Returns:

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:

  • max_runtime (float, default: 3600 ) –

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

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • 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: