Integer Knapsack Problem (IKP) Example

Download Notebook

The Knapsack Problem is a classic combinatorial optimization problem: given a set of items with integer weights and values, select items to maximize total value while keeping total weight within the knapsack's capacity.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.integer_knapsack_problem import (
    IkpCollection,
    IkpData,
    IkpFormulation,
    IkpInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a simple knapsack instance with 5 items using the from_arrays() factory method. The knapsack has a weight capacity of 50, and individual item weights range from 5 to 30 — typically much smaller than the capacity, since the goal is to fit multiple items into the knapsack.

weights = np.array([10, 20, 30, 15, 5])
values = np.array([60.0, 100.0, 120.0, 80.0, 30.0])
capacity = 50

data = IkpData.from_arrays(w=weights, c=values, w_cap=capacity)
print(data.to_string())

Integer Knapsack Problem:
  Number of items: 5
  Knapsack capacity: 50
  Weights: [10 20 30 15  5]
  Values: [ 60. 100. 120.  80.  30.]

Plot Data

Visualize item weights and values.

data.plot()

<Axes: title={'center': 'IKP — Item Weights vs. Values'}, xlabel='Weight', ylabel='Value'>

Create Formulation

Maximize total value of selected items subject to a capacity constraint.

formulation = IkpFormulation()
print(formulation.to_string(data))

Integer Knapsack Problem Formulation:
  Items: 5
  Capacity: 50

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if item i is selected
  Total: 5 binary variables

Objective:
  maximize sum_i c[i] * x[i]  for i = 0, ..., 4

Constraints:
  1. Capacity constraint (1 constraint):
     sum_{i=0}^{4} w[i] * x[i] <= 50

Create Instance

Combine data and formulation into a solvable instance.

instance = IkpInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Integer Knapsack Problem:
  Number of items: 5
  Knapsack capacity: 50
  Weights: [10 20 30 15  5]
  Values: [ 60. 100. 120.  80.  30.]
Formulation:Integer Knapsack Problem Formulation:
  Items: 5
  Capacity: 50

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if item i is selected
  Total: 5 binary variables

Objective:
  maximize sum_i c[i] * x[i]  for i = 0, ..., 4

Constraints:
  1. Capacity constraint (1 constraint):
     sum_{i=0}^{4} w[i] * x[i] <= 50

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Integer Knapsack Problem Solution:
  Selected items (indices): [0, 1, 3, 4]
  Total weight: 50
  Total value: 270.0
  Is valid: True
  Number of items selected: 4

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'IKP — Solution'}, xlabel='Weight', ylabel='Value'>

Collections

Generate benchmark collections of IKP instances for batch processing. Several generators are available, each producing instances with different weight-value correlation characteristics.

collection = IkpCollection.from_random(
    min_num_items=5,
    max_num_items=8,
    num_instances=2,
    capacity=100,
    weight_max=30,
    value_max=40,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)

Model: integer_knapsack_problem<integer_knapsack_problem>
Maximize
  35 * x_0 + 4 * x_1 + 28 * x_2 + 9 * x_3 + 4 * x_4
Subject To
  capacity_constraint: 3 * x_0 + 24 * x_1 + 20 * x_2 + 14 * x_3 + 13 * x_4 <=
    100
Binary
  x_0 x_1 x_2 x_3 x_4