Skip to content

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

  • 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

Print the data.

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

Create IkpData from weight and value arrays.

Parameters:

  • w (ndarray) –

    Array of item weights (integers).

  • c (ndarray) –

    Array of item values (floats).

  • w_cap (int) –

    Knapsack capacity.

Returns:

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

  • n_items (int, default: 20 ) –

    Number of items, by default 20

  • capacity (int, default: 25 ) –

    Knapsack capacity, by default 25

  • weight_max (int, default: 50 ) –

    Maximum weight for random generation, by default 50

  • value_max (int, default: 50 ) –

    Maximum value for random generation, by default 50

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

    Random seed for reproducibility, by default None

Returns:

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

  • data (IkpData) –

    The IKP instance data containing weights, values, and capacity.

Returns:

  • Model –

    A optimization model ready to be solved.

Raises:

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:

  • solution (Solution) –

    The solution containing variable assignments.

  • data (IkpData) –

    The original IKP instance data.

Returns:

  • IkpSolution –

    A structured solution object with selected items and metrics.

Raises:

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

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

    Problem data. When provided, items are shown as a scatter with selection highlighting.

  • 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

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:

  • min_num_items (int) –

    Minimum number of items per instance.

  • max_num_items (int) –

    Maximum number of items per instance.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each item count, by default 1.

  • weight_range (tuple[int, int], default: (1, 100) ) –

    Range (min, max) for random weights, by default (1, 100).

  • value_range (tuple[int, int], default: (1, 100) ) –

    Range (min, max) for random values, by default (1, 100).

  • capacity_ratio (float, default: 0.5 ) –

    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.

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

    Random seed for reproducible results, by default None.

Returns:

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

  • min_num_items (int) –

    Minimum number of items per instance.

  • max_num_items (int) –

    Maximum number of items per instance.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each item count, by default 1.

  • weight_range (tuple[int, int], default: (1, 100) ) –

    Range (min, max) for random weights, by default (1, 100).

  • correlation_range (int, default: 20 ) –

    Range for correlation offset, by default 20. Values will be w_i ± correlation_range.

  • capacity_ratio (float, default: 0.5 ) –

    Capacity as a ratio of total weight (0-1), by default 0.5.

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

    Random seed for reproducible results, by default None.

Returns:

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

  • min_num_items (int) –

    Minimum number of items per instance.

  • max_num_items (int) –

    Maximum number of items per instance.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each item count, by default 1.

  • weight_range (tuple[int, int], default: (1, 100) ) –

    Range (min, max) for random weights, by default (1, 100).

  • offset (int, default: 10 ) –

    Fixed offset added to weights to get values, by default 10. c_i = w_i + offset.

  • capacity_ratio (float, default: 0.5 ) –

    Capacity as a ratio of total weight (0-1), by default 0.5.

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

    Random seed for reproducible results, by default None.

Returns:

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

  • min_num_items (int) –

    Minimum number of items per instance.

  • max_num_items (int) –

    Maximum number of items per instance.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each item count, by default 1.

  • weight_range (tuple[int, int], default: (1, 100) ) –

    Range (min, max) for random weights, by default (1, 100).

  • capacity_ratio (float, default: 0.5 ) –

    Capacity as a ratio of total weight (0-1), by default 0.5.

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

    Random seed for reproducible results, by default None.

Returns:

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

  • min_num_items (int) –

    Minimum number of items per instance.

  • max_num_items (int) –

    Maximum number of items per instance.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each item count, by default 1.

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

    Fixed capacity for all instances. If None, capacity will be set to approximately half the sum of all weights, by default None.

  • weight_max (int, default: 50 ) –

    Maximum weight for random generation, by default 50.

  • value_max (int, default: 50 ) –

    Maximum value for random generation, by default 50.

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

    Random seed for reproducible results, by default None.

Returns:

  • 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,
... )