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	Type	Description
`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:

Name	Type	Description	Default
`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 MKP data.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`values`	`list[float]`	Value of each item.	required
`weights`	`list[float]`	Weight of each item.	required
`capacities`	`list[float]`	Capacity of each knapsack.	required
`item_names`	`list[int \| str] \| None`	Names for each item. Defaults to `0, 1, ...`.	`None`
`knapsack_names`	`list[int \| str] \| None`	Names for each knapsack. Defaults to `0, 1, ...`.	`None`

Returns:

Type	Description
`MultiKnapsackData`	The MKP data instance.

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:

Name	Type	Description	Default
`n_items`	`int`	Number of items, by default 5.	`5`
`n_knapsacks`	`int`	Number of knapsacks, by default 2.	`2`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`MultiKnapsackData`	A randomly generated MKP instance.

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:

Name	Type	Description	Default
`data`	`MultiKnapsackData`	The problem data.	required

Returns:

Type	Description
`str`	String representation of the formulation.

`formulate(data: MultiKnapsackData) -> Model` `staticmethod`

Formulate the MKP using a constraint-based approach.

Parameters:

Name	Type	Description	Default
`data`	`MultiKnapsackData`	The problem data.	required

Returns:

Type	Description
`Model`	A Luna Model ready to be solved.

Raises:

Type	Description
`EmptyDataError`	If there are no items or no knapsacks.

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

Extract the MKP solution from the solver result.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution containing variable assignments.	required
`data`	`MultiKnapsackData`	The original problem data.	required

Returns:

Type	Description
`MultiKnapsackSolution`	Structured solution with packing, value, and validity.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find a solution.

Solution

Solution model for Multiple Knapsack use case.

`MultiKnapsackSolution`

Bases: UcSolution

Solution for the Multiple Knapsack Problem (MKP).

Attributes:

Name	Type	Description
`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:

Name	Type	Description	Default
`data`	`MultiKnapsackData \| None`	Problem data. Required for capacities and labels.	`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.

Raises:

Type	Description
`ValueError`	If data is `None`.

`to_string() -> str`

Return a string describing the solution.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`min_items`	`int \| None`	Minimum number of items.	`None`
`max_items`	`int \| None`	Maximum number of items.	`None`
`n_knapsacks`	`int`	Number of knapsacks, by default 2.	`2`
`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_items`/`max_items`, by default None.	`None`

Returns:

Type	Description
`MultiKnapsackCollection`	Collection containing generated instances.

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:

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.

Multiple Knapsack API Reference

Data

MultiKnapsackData

n_items: int property

n_knapsacks: int property

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

to_string() -> str

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

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

Formulation

MultiKnapsackFormulation

to_string(data: MultiKnapsackData) -> str staticmethod

formulate(data: MultiKnapsackData) -> Model staticmethod

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

Solution

MultiKnapsackSolution

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

to_string() -> str

Instance

MultiKnapsackInstance

Collection

MultiKnapsackCollection

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

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

`MultiKnapsackData`

`n_items: int` `property`

`n_knapsacks: int` `property`

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

`to_string() -> str`

`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`

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

`MultiKnapsackFormulation`

`to_string(data: MultiKnapsackData) -> str` `staticmethod`

`formulate(data: MultiKnapsackData) -> Model` `staticmethod`

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

`MultiKnapsackSolution`

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

`to_string() -> str`

`MultiKnapsackInstance`

`MultiKnapsackCollection`

`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`

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