Skip to content

Multiple Knapsack API Reference

Data

Data model for Multiple Knapsack use case.

MultiKnapsackData

Bases: UcData

Data for the Multiple Knapsack Problem (MKP).

Given n items, each with a value and a weight, and m knapsacks, each with a weight capacity, pack a subset of the items into the knapsacks so that each item is placed in at most one knapsack, no knapsack exceeds its capacity, and the total value of packed items is maximized.

Attributes:

  • name (Literal['multiple_knapsack_problem']) –

    Identifier for this data type.

  • values (NumPyArray) –

    Value of each item. Length equals the number of items n.

  • weights (NumPyArray) –

    Weight of each item. Length equals the number of items n.

  • capacities (NumPyArray) –

    Capacity of each knapsack. Length equals the number of knapsacks m.

  • item_names (list[int | str]) –

    Names for each item. Defaults to 0, 1, ....

  • knapsack_names (list[int | str]) –

    Names for each knapsack. Defaults to 0, 1, ....

Examples:

>>> data = MultiKnapsackData.from_values_and_weights(
...     values=[5.0, 3.0],
...     weights=[2.0, 2.0],
...     capacities=[10.0],
... )

n_items: int property

Return the number of items.

n_knapsacks: int property

Return the number of knapsacks.

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

Plot the items as a value-vs-weight scatter.

Parameters:

  • 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 MKP data.

Returns:

  • str –

    String representation of the data.

from_values_and_weights(values: list[float], weights: list[float], capacities: list[float], item_names: list[int | str] | None = None, knapsack_names: list[int | str] | None = None) -> MultiKnapsackData staticmethod

Create MultiKnapsackData from item values, weights and capacities.

Parameters:

  • values (list[float]) –

    Value of each item.

  • weights (list[float]) –

    Weight of each item.

  • capacities (list[float]) –

    Capacity of each knapsack.

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

    Names for each item. Defaults to 0, 1, ....

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

    Names for each knapsack. Defaults to 0, 1, ....

Returns:

Examples:

>>> data = MultiKnapsackData.from_values_and_weights(
...     values=[5.0, 3.0, 4.0],
...     weights=[2.0, 2.0, 3.0],
...     capacities=[4.0, 4.0],
... )

generate_random(n_items: int = 5, n_knapsacks: int = 2, seed: int | None = None) -> MultiKnapsackData staticmethod

Generate a random Multiple Knapsack instance.

Item values and weights are drawn uniformly, and knapsack capacities are scaled so that only a fraction of the items fit.

Parameters:

  • n_items (int, default: 5 ) –

    Number of items, by default 5.

  • n_knapsacks (int, default: 2 ) –

    Number of knapsacks, by default 2.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> data = MultiKnapsackData.generate_random(n_items=6, n_knapsacks=2, seed=42)

Formulation

Formulation for Multiple Knapsack use case.

MultiKnapsackFormulation

Bases: UcFormulation[MultiKnapsackData, MultiKnapsackSolution]

Constraint-based formulation for the Multiple Knapsack Problem.

Mathematical Formulation 
Given:
    - n items, indexed i = 0, ..., n-1
    - m knapsacks, indexed k = 0, ..., m-1
    - v_i: value of item i
    - w_i: weight of item i
    - C_k: capacity of knapsack k

Decision Variables:
    x_ik in {0, 1} for each item i and knapsack k
        x_ik = 1 if item i is placed in knapsack k.

Objective (maximize):
    maximize  sum_i sum_k v_i * x_ik

Constraints:
    1. Each item placed in at most one knapsack:
       sum_k x_ik <= 1   for all i
    2. Knapsack capacity:
       sum_i w_i * x_ik <= C_k   for all k
References
  • Wikipedia: https://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsacks

to_string(data: MultiKnapsackData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: MultiKnapsackData) -> Model staticmethod

Formulate the MKP using a constraint-based approach.

Parameters:

Returns:

  • Model –

    A Luna Model ready to be solved.

Raises:

interpret(solution: Solution, data: MultiKnapsackData) -> MultiKnapsackSolution staticmethod

Extract the MKP solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution containing variable assignments.

  • data (MultiKnapsackData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Multiple Knapsack use case.

MultiKnapsackSolution

Bases: UcSolution

Solution for the Multiple Knapsack Problem (MKP).

Attributes:

  • name (Literal['multiple_knapsack_problem']) –

    Identifier for this solution type.

  • packing (dict[int | str, int | str]) –

    Mapping from each packed item to the knapsack it is placed in. Items that are left out do not appear.

  • total_value (float) –

    Total value of all packed items (the maximized objective).

  • knapsack_loads (dict[int | str, float]) –

    Total weight packed into each knapsack.

  • is_valid (bool) –

    Whether the solution is valid (no item in more than one knapsack and no knapsack capacity exceeded).

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

Plot the packed weight per knapsack against its capacity.

Parameters:

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

    Problem data. Required for capacities and labels.

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

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

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for Multiple Knapsack use case.

MultiKnapsackInstance

Bases: UcInstance[MultiKnapsackData, MultiKnapsackFormulation, MultiKnapsackSolution]

Instance combining data and formulation for the Multiple Knapsack Problem.

Collection

Collection of Multiple Knapsack instances.

MultiKnapsackCollection

Bases: UcInstanceCollection[MultiKnapsackInstance]

Collection of Multiple Knapsack instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_items: int | None = None, max_items: int | None = None, n_knapsacks: int = 2, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MultiKnapsackCollection classmethod

Generate random Multiple Knapsack instances.

Parameters:

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

    Minimum number of items.

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

    Maximum number of items.

  • n_knapsacks (int, default: 2 ) –

    Number of knapsacks, by default 2.

  • 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_items/max_items, by default None.

Returns:

Examples:

>>> collection = MultiKnapsackCollection.from_random(
...     min_items=4,
...     max_items=5,
...     num_instances=2,
...     seed=42,
... )

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: