Integer Knapsack Problem (IKP) API Reference

Data

Data model for Ikp use case.

`IkpData`

Bases: UcData

Data for the Knapsack with Integer Weights Problem (IKP) use case.

This class encapsulates all necessary information to define and solve a Knapsack with Integer Weights problem instance. Given a knapsack that can only carry a w_cap and a set of objects, each object having a weight w and a value c, the IKP tries to find objects so that the sum of their values is maximized while, at the same time, the sum of their weights does not exceed the capacity of the knapsack.

Attributes:

Name	Type	Description
`name`	`Literal['integer_knapsack_problem']`	A constant identifier for this data type, always set to "integer_knapsack_problem". Used for registration and type identification in the use case registry.
`w`	`NumPyArray`	The weight of each object as a 1D NumPy array of integers. Example: np.array([10, 20, 30])
`c`	`NumPyArray`	The value of each object as a 1D NumPy array of floats. Example: np.array([60.0, 100.0, 120.0])
`w_cap`	`int`	The maximum weight that the knapsack can carry. Example: 50

Examples:

Create a simple 3-item knapsack instance:

>>> ikp = IkpData(
...     name="integer_knapsack_problem",
...     w=np.array([10, 20, 30]),
...     c=np.array([60.0, 100.0, 120.0]),
...     w_cap=50,
... )

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

Plot item weights vs. values as a scatter chart.

Each item is shown as a point with weight on the x-axis and value on the y-axis. A text box shows the knapsack capacity.

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`

Print the data.

`from_arrays(w: np.ndarray, c: np.ndarray, w_cap: int) -> IkpData` `staticmethod`

Create IkpData from weight and value arrays.

Parameters:

Name	Type	Description	Default
`w`	`ndarray`	Array of item weights (integers).	required
`c`	`ndarray`	Array of item values (floats).	required
`w_cap`	`int`	Knapsack capacity.	required

Returns:

Type	Description
`IkpData`	The created IKP data instance.

`generate_random(n_items: int = 20, capacity: int = 25, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpData` `staticmethod`

Generate a random IKP instance.

Parameters:

Name	Type	Description	Default
`n_items`	`int`	Number of items, by default 20	`20`
`capacity`	`int`	Knapsack capacity, by default 25	`25`
`weight_max`	`int`	Maximum weight for random generation, by default 50	`50`
`value_max`	`int`	Maximum value for random generation, by default 50	`50`
`seed`	`int \| None`	Random seed for reproducibility, by default None	`None`

Returns:

Type	Description
`IkpData`	A randomly generated IKP data instance.

Formulation

Formulation for Ikp use case.

`IkpFormulation`

Bases: UcFormulation[IkpData, IkpSolution]

Formulation for the Knapsack with Integer Weights Problem (IKP) use case.

This class provides a constraint-based formulation to solve IKP using optimization.

Mathematical Formulation

The knapsack problem is formulated as:

Decision Variables: x_i ∈ {0,1}: 1 if item i is selected, 0 otherwise

Objective: maximize Σ_i (c_i * x_i)

Constraints: Σ_i (w_i * x_i) ≤ W (capacity constraint)

The solver automatically handles constraint enforcement without requiring manual penalty terms or slack variables.

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

Print the formulation.

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

Formulate the use case as a constrained-based optimization model.

Creates a constraint-based formulation for the Knapsack with Integer Weights Problem using decision variables and a capacity constraint.

Parameters:

Name	Type	Description	Default
`data`	`IkpData`	The IKP instance data containing weights, values, and capacity.	required

Returns:

Type	Description
`Model`	A optimization model ready to be solved.

Raises:

Type	Description
`DataShapeMismatchError`	If weights and values have different lengths.
`InvalidValueError`	If capacity is negative.

`interpret(solution: Solution, data: IkpData) -> IkpSolution` `staticmethod`

Interpret the solution.

Extracts the selected items from the solution and computes solution metrics like total weight, total value, and validity.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solution containing variable assignments.	required
`data`	`IkpData`	The original IKP instance data.	required

Returns:

Type	Description
`IkpSolution`	A structured solution object with selected items and metrics.

Raises:

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

Solution

Solution model for Ikp use case.

`IkpSolution`

Bases: UcSolution

Solution for the Knapsack with Integer Weights Problem (IKP) use case.

This class represents a solution to an IKP instance, containing the selected items, their total weight and value, and whether the solution is valid (satisfies all constraints).

Attributes:

Name	Type	Description
`name`	`Literal['integer_knapsack_problem']`	A constant identifier for this solution type, always set to "integer_knapsack_problem".
`selected_indices`	`list[int]`	A list of indices of the items that were selected for the knapsack. Example: [0, 2, 5] means items at positions 0, 2, and 5 are selected.
`total_weight`	`int`	The total weight of all selected items. Should not exceed the knapsack capacity for a valid solution.
`total_value`	`float`	The total value of all selected items. This is the objective value that we want to maximize.
`is_valid`	`bool`	Whether the solution satisfies all constraints: - Total weight does not exceed knapsack capacity - Each item is selected at most once

Examples:

A valid solution where items 0, 2, and 3 are selected:

>>> solution = IkpSolution(
...     name="integer_knapsack_problem",
...     selected_indices=[0, 2, 3],
...     total_weight=45,
...     total_value=250.0,
...     is_valid=True,
... )

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

Plot the knapsack solution.

When data is provided the plot shows a scatter of item weights vs. values with selected items highlighted in green and unselected items in grey, with a colour legend. A text box shows capacity, total weight and total value. Without data a simple bar chart of total value and total weight is drawn.

Parameters:

Name	Type	Description	Default
`data`	`IkpData \| None`	Problem data. When provided, items are shown as a scatter with selection highlighting.	`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`

Print the solution.

Instance

Instance model for Ikp use case.

`IkpInstance`

Bases: UcInstance[IkpData, IkpFormulation, IkpSolution]

Instance combining data and formulation for Ikp.

Collection

Collection of Ikp instances.

`IkpCollection`

Bases: UcInstanceCollection[IkpInstance]

Collection of Integer Knapsack Problem instances.

This collection provides methods to generate knapsack instances with various correlation patterns between weights and values, which are commonly used in knapsack problem benchmarks.

`from_uncorrelated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), value_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

Generate uncorrelated knapsack instances.

In uncorrelated instances, weights and values are independent random integers. This is the simplest type of knapsack instance and is often used as a baseline.

Parameters:

Name	Type	Description	Default
`min_num_items`	`int`	Minimum number of items per instance.	required
`max_num_items`	`int`	Maximum number of items per instance.	required
`num_instances`	`int`	Number of instances to generate for each item count, by default 1.	`1`
`weight_range`	`tuple[int, int]`	Range (min, max) for random weights, by default (1, 100).	`(1, 100)`
`value_range`	`tuple[int, int]`	Range (min, max) for random values, by default (1, 100).	`(1, 100)`
`capacity_ratio`	`float`	Capacity as a ratio of total weight (0-1), by default 0.5. E.g., 0.5 means capacity is half the sum of all weights.	`0.5`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`IkpCollection`	Collection containing generated IKP instances.

Examples:

>>> collection = IkpCollection.from_uncorrelated(
...     min_num_items=5,
...     max_num_items=10,
...     num_instances=3,
...     seed=42,
... )

`from_weakly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), correlation_range: int = 20, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

Generate weakly correlated knapsack instances.

In weakly correlated instances, each value is related to its weight within a random range: c_i = w_i + R, where R is a random integer in [-correlation_range, +correlation_range].

Parameters:

Name	Type	Description	Default
`min_num_items`	`int`	Minimum number of items per instance.	required
`max_num_items`	`int`	Maximum number of items per instance.	required
`num_instances`	`int`	Number of instances to generate for each item count, by default 1.	`1`
`weight_range`	`tuple[int, int]`	Range (min, max) for random weights, by default (1, 100).	`(1, 100)`
`correlation_range`	`int`	Range for correlation offset, by default 20. Values will be w_i ± correlation_range.	`20`
`capacity_ratio`	`float`	Capacity as a ratio of total weight (0-1), by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`IkpCollection`	Collection containing generated IKP instances.

Examples:

>>> collection = IkpCollection.from_weakly_correlated(
...     min_num_items=10,
...     max_num_items=20,
...     correlation_range=10,
...     seed=42,
... )

`from_strongly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), offset: int = 10, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

Generate strongly correlated knapsack instances.

In strongly correlated instances, each value is directly related to its weight with a fixed offset: c_i = w_i + offset. This creates instances where items with higher weights tend to have higher values.

Parameters:

Name	Type	Description	Default
`min_num_items`	`int`	Minimum number of items per instance.	required
`max_num_items`	`int`	Maximum number of items per instance.	required
`num_instances`	`int`	Number of instances to generate for each item count, by default 1.	`1`
`weight_range`	`tuple[int, int]`	Range (min, max) for random weights, by default (1, 100).	`(1, 100)`
`offset`	`int`	Fixed offset added to weights to get values, by default 10. c_i = w_i + offset.	`10`
`capacity_ratio`	`float`	Capacity as a ratio of total weight (0-1), by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`IkpCollection`	Collection containing generated IKP instances.

Examples:

>>> collection = IkpCollection.from_strongly_correlated(
...     min_num_items=5,
...     max_num_items=15,
...     offset=20,
...     seed=42,
... )

`from_subset_sum(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

Generate subset-sum knapsack instances.

Subset-sum instances are a special case where values equal weights (c_i = w_i). This reduces the knapsack problem to the subset-sum problem, where the goal is to find a subset with maximum weight that doesn't exceed the capacity.

Parameters:

Name	Type	Description	Default
`min_num_items`	`int`	Minimum number of items per instance.	required
`max_num_items`	`int`	Maximum number of items per instance.	required
`num_instances`	`int`	Number of instances to generate for each item count, by default 1.	`1`
`weight_range`	`tuple[int, int]`	Range (min, max) for random weights, by default (1, 100).	`(1, 100)`
`capacity_ratio`	`float`	Capacity as a ratio of total weight (0-1), by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`IkpCollection`	Collection containing generated subset-sum instances.

Examples:

>>> collection = IkpCollection.from_subset_sum(
...     min_num_items=10,
...     max_num_items=15,
...     capacity_ratio=0.3,
...     seed=42,
... )

`from_random(min_num_items: int, max_num_items: int, num_instances: int = 1, *, capacity: int | None = None, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpCollection` `classmethod`

Generate random knapsack instances with fixed parameters.

This method generates instances using the simple random generation approach with fixed maximum values for weights and values, and optionally a fixed capacity.

Parameters:

Name	Type	Description	Default
`min_num_items`	`int`	Minimum number of items per instance.	required
`max_num_items`	`int`	Maximum number of items per instance.	required
`num_instances`	`int`	Number of instances to generate for each item count, by default 1.	`1`
`capacity`	`int \| None`	Fixed capacity for all instances. If None, capacity will be set to approximately half the sum of all weights, by default None.	`None`
`weight_max`	`int`	Maximum weight for random generation, by default 50.	`50`
`value_max`	`int`	Maximum value for random generation, by default 50.	`50`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`IkpCollection`	Collection containing generated random IKP instances.

Examples:

>>> collection = IkpCollection.from_random(
...     min_num_items=5,
...     max_num_items=10,
...     capacity=100,
...     weight_max=30,
...     value_max=40,
...     seed=42,
... )

Integer Knapsack Problem (IKP) API Reference

Data

IkpData

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

to_string() -> str

from_arrays(w: np.ndarray, c: np.ndarray, w_cap: int) -> IkpData staticmethod

generate_random(n_items: int = 20, capacity: int = 25, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpData staticmethod

Formulation

IkpFormulation

to_string(data: IkpData) -> str staticmethod

formulate(data: IkpData) -> Model staticmethod

interpret(solution: Solution, data: IkpData) -> IkpSolution staticmethod

Solution

IkpSolution

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

to_string() -> str

Instance

IkpInstance

Collection

IkpCollection

from_uncorrelated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), value_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection classmethod

from_weakly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), correlation_range: int = 20, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection classmethod

from_strongly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), offset: int = 10, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection classmethod

from_subset_sum(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection classmethod

from_random(min_num_items: int, max_num_items: int, num_instances: int = 1, *, capacity: int | None = None, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpCollection classmethod

`IkpData`

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

`to_string() -> str`

`from_arrays(w: np.ndarray, c: np.ndarray, w_cap: int) -> IkpData` `staticmethod`

`generate_random(n_items: int = 20, capacity: int = 25, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpData` `staticmethod`

`IkpFormulation`

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

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

`interpret(solution: Solution, data: IkpData) -> IkpSolution` `staticmethod`

`IkpSolution`

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

`to_string() -> str`

`IkpInstance`

`IkpCollection`

`from_uncorrelated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), value_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

`from_weakly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), correlation_range: int = 20, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

`from_strongly_correlated(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), offset: int = 10, capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

`from_subset_sum(min_num_items: int, max_num_items: int, num_instances: int = 1, *, weight_range: tuple[int, int] = (1, 100), capacity_ratio: float = 0.5, seed: int | None = None) -> IkpCollection` `classmethod`

`from_random(min_num_items: int, max_num_items: int, num_instances: int = 1, *, capacity: int | None = None, weight_max: int = 50, value_max: int = 50, seed: int | None = None) -> IkpCollection` `classmethod`