Skip to content

Quadratic Knapsack Problem (QKP) API Reference

Data

Data model for Quadratic Knapsack use case.

QuadraticKnapsackData

Bases: UcData

Data for the Quadratic Knapsack Problem (QKP) use case.

The Quadratic Knapsack Problem extends the classical knapsack by assigning values to pairs of items rather than individual items. The objective is to select a subset of items maximizing the total pairwise interaction value while staying within a budget constraint.

Attributes:

  • name (Literal['quadratic_knapsack']) –

    A constant identifier for this data type.

  • interaction_matrix (NumPyArray) –

    Symmetric n x n matrix where element [i, j] represents the value obtained when both items i and j are selected.

  • costs (NumPyArray) –

    Cost of selecting each item.

  • budget (float) –

    Maximum total cost allowed.

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

Plot the interaction matrix as a heatmap and item costs with budget.

When ax is None a figure with two subplots is created: the left panel shows the interaction-value heatmap and the right panel shows per-item costs as a bar chart with a dashed line for the budget constraint. When an existing ax is provided, only the heatmap is drawn on that axes.

Parameters:

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

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

Returns:

  • Axes | tuple[Axes, Axes] –

    A single axes when ax is provided, or a (heatmap, costs) tuple when a new figure is created.

to_string() -> str

Return a string describing the data.

from_matrix(interaction_matrix: list[list[float]] | NDArray[np.float32], costs: list[float] | NDArray[np.float32], budget: float) -> QuadraticKnapsackData staticmethod

Create QuadraticKnapsackData from an interaction matrix.

Parameters:

  • interaction_matrix (list[list[float]] | NDArray) –

    Symmetric n x n interaction matrix.

  • costs (list[float] | NDArray) –

    Cost per item.

  • budget (float) –

    Maximum total cost.

Returns:

generate_random(n_items: int = 5, max_interaction: int = 10, max_cost: int = 10, size: int | None = None, seed: int | None = None) -> QuadraticKnapsackData staticmethod

Generate a random Quadratic Knapsack instance.

Parameters:

  • n_items (int, default: 5 ) –

    Number of items, by default 5.

  • max_interaction (int, default: 10 ) –

    Maximum interaction value, by default 10.

  • max_cost (int, default: 10 ) –

    Maximum cost per item, by default 10.

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

    If provided, overrides n_items (for collection compatibility).

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

    Random seed for reproducibility, by default None.

Returns:

Formulation

Formulation for Quadratic Knapsack use case.

QuadraticKnapsackFormulation

Bases: UcFormulation[QuadraticKnapsackData, QuadraticKnapsackSolution]

Constraint-based formulation for the Quadratic Knapsack Problem.

Mathematical Formulation 
Decision Variables:
    x_i in {0,1}: 1 if item i is selected, 0 otherwise

Objective:
    ``maximize sum_{i,j} interaction[i][j] * x_i * x_j``

Constraints:
    sum_i costs[i] * x_i <= budget

to_string(data: QuadraticKnapsackData) -> str staticmethod

Return a string describing the formulation.

formulate(data: QuadraticKnapsackData) -> Model staticmethod

Formulate the Quadratic Knapsack as an optimization model.

Parameters:

Returns:

  • Model –

    A model ready to be solved.

interpret(solution: Solution, data: QuadraticKnapsackData) -> QuadraticKnapsackSolution staticmethod

Extract solution from solver result.

Parameters:

Returns:

Raises:

Solution

Solution model for Quadratic Knapsack use case.

QuadraticKnapsackSolution

Bases: UcSolution

Solution for the Quadratic Knapsack Problem (QKP) use case.

Attributes:

  • name (Literal['quadratic_knapsack']) –

    Identifier for this solution type.

  • selected_items (list[int]) –

    Indices of the selected items.

  • total_value (float) –

    Total interaction value of the selected items.

  • total_cost (float) –

    Total cost of the selected items.

  • is_valid (bool) –

    Whether the solution satisfies the budget constraint (total_cost <= budget).

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

Plot the selected items.

Parameters:

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

    Problem data for additional 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.

Instance

Instance model for QuadraticKnapsack use case.

QuadraticKnapsackInstance

Bases: UcInstance[QuadraticKnapsackData, QuadraticKnapsackFormulation, QuadraticKnapsackSolution]

Instance combining data and formulation for QuadraticKnapsack.

Collection

Collection of Quadratic Knapsack instances.

QuadraticKnapsackCollection

Bases: UcInstanceCollection[QuadraticKnapsackInstance]

Collection of Quadratic Knapsack 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) -> QuadraticKnapsackCollection classmethod

Generate random Quadratic Knapsack instances.

Parameters:

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

    Minimum number of items.

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

    Maximum number of items.

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