Multiple Knapsack Example

Download Notebook

The Multiple Knapsack Problem packs a subset of n items (each with a value and weight) into m capacity-limited knapsacks. Each item goes into at most one knapsack, no knapsack exceeds its capacity, and the total value of packed items is maximized. It is NP-hard and generalizes the classic 0/1 knapsack problem.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.multiple_knapsack_problem import (
    MultiKnapsackCollection,
    MultiKnapsackData,
    MultiKnapsackFormulation,
    MultiKnapsackInstance,
)

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

Create Data

Build an instance from item values, weights and knapsack capacities using the from_values_and_weights factory.

data = MultiKnapsackData.from_values_and_weights(
    values=[10.0, 7.0, 5.0, 8.0, 3.0],
    weights=[5.0, 4.0, 3.0, 6.0, 2.0],
    capacities=[8.0, 7.0],
)
print(data.to_string())

Multiple Knapsack Problem Data:
  Items: 5
  Knapsacks: 2
  Capacities: ['8.0', '7.0']
  Total value: 33.0
  Total weight: 20.0

Plot Data

Visualize the items in value-vs-weight space.

data.plot()

<Axes: title={'center': 'Multiple Knapsack — 5 items, 2 knapsacks'}, xlabel='Weight', ylabel='Value'>

Create Formulation

Maximize total packed value subject to per-item and per-knapsack constraints.

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

Multiple Knapsack Problem Formulation:
  Items: 5
  Knapsacks: 2

Decision Variables:
  x_ik in {0,1} for i = 0, ..., 4, k = 0, ..., 1
  Total: 10 binary variables

Objective:
  maximize  sum_i sum_k v_i * x_ik

Constraints:
  1. At most one knapsack: sum_k x_ik <= 1 for all i  (5 constraints)
  2. Capacity: sum_i w_i * x_ik <= C_k for all k  (2 constraints)

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Multiple Knapsack Problem Data:
  Items: 5
  Knapsacks: 2
  Capacities: ['8.0', '7.0']
  Total value: 33.0
  Total weight: 20.0
Formulation:Multiple Knapsack Problem Formulation:
  Items: 5
  Knapsacks: 2

Decision Variables:
  x_ik in {0,1} for i = 0, ..., 4, k = 0, ..., 1
  Total: 10 binary variables

Objective:
  maximize  sum_i sum_k v_i * x_ik

Constraints:
  1. At most one knapsack: sum_k x_ik <= 1 for all i  (5 constraints)
  2. Capacity: sum_i w_i * x_ik <= C_k for all k  (2 constraints)

Formulate Model

Translate the instance into a mixed-integer 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/.worktrees/multiple_knapsack_problem/.venv/lib/python3.13
/site-packages/rich/live.py:260: UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

2026-06-17 09:08:57 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

Multiple Knapsack Problem Solution:
  Packing: 0 -> 1, 1 -> 0, 2 -> 0, 4 -> 1
  Total value: 25.00
  Knapsack loads: 0: 7.0, 1: 7.0
  Valid: True

Plot Solution

Visualize the packed weight per knapsack against its capacity.

uc_solution.plot(data)

<Axes: title={'center': 'Multiple Knapsack Solution — value: 25.0'}, xlabel='Knapsack', ylabel='Weight'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = MultiKnapsackCollection.from_random(min_items=4, max_items=5, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: multiple_knapsack_problem<s42_i4_n0>
Maximize
  2.8716358549829786 * x_0_0 + 2.8716358549829786 * x_0_1
  + 3.8584655971645923 * x_1_0 + 3.8584655971645923 * x_1_1
  + 2.248919008072832 * x_2_0 + 2.248919008072832 * x_2_1
  + 7.903351786733379 * x_3_0 + 7.903351786733379 * x_3_1
Subject To
  item_0: x_0_0 + x_0_1 <= 1
  item_1: x_1_0 + x_1_1 <= 1
  item_2: x_2_0 + x_2_1 <= 1
  item_3: x_3_0 + x_3_1 <= 1
  capacity_0: 6.4776386586482095 * x_0_0 + 1.6214616397519919 * x_1_0
    + 1.0372020523902665 * x_2_0 + 9.3202717031276 * x_3_0 <= 4.614143513479517
  capacity_1: 6.4776386586482095 * x_0_1 + 1.6214616397519919 * x_1_1
    + 1.0372020523902665 * x_2_1 + 9.3202717031276 * x_3_1 <= 4.614143513479517
Binary
  x_0_0 x_0_1 x_1_0 x_1_1 x_2_0 x_2_1 x_3_0 x_3_1