Bin Packing Problem (BPP) Example

Download Notebook

The Bin Packing Problem (BPP) asks to pack a set of items with given weights into the minimum number of fixed-capacity bins. It is NP-hard.

import getpass
import os

import matplotlib.pyplot as plt
import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.bin_packing_problem import (
    BppCollection,
    BppData,
    BppFormulation,
    BppInstance,
)

load_dotenv()

if "LUNA_API_KEY" not in os.environ:
    # Prompt securely for the key if not already set
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define the problem data.

# Define item weights and bin capacity
item_weights = np.array([4.5, 2.3, 6.1, 3.8, 5.2, 1.9, 4.0, 2.7])
bin_capacity = 10.0
item_names = ["A", "B", "C", "D", "E", "F", "G", "H"]

bpp_data = BppData.from_weights(
    item_weights=item_weights,
    bin_capacity=bin_capacity,
    item_names=item_names,
)

print(bpp_data.to_string())

Bin Packing Data:
  Items: 8
  Item names: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
  Item weights: [4.5 2.3 6.1 3.8 5.2 1.9 4.  2.7]
  Bin capacity: 10.0
  Max bins: 8

Alternative: Generate Random Data

You can also generate random problem instances:

# Generate a random BPP instance with 6 items
random_data = BppData.generate_random(
    n_items=6,
    bin_capacity=10.0,
    seed=42,
)

print(random_data.to_string())

Bin Packing Data:
  Items: 6
  Item names: ['0', '1', '2', '3', '4', '5']
  Item weights: [7.8 4.4 8.6 7.  1.  9.8]
  Bin capacity: 10.0
  Max bins: 6

Plot Data

Visualize the item weights relative to bin capacity.

ax = bpp_data.plot()
plt.show()

png

Create Formulation

Define the optimization formulation.

bpp_formulation = BppFormulation()
print(bpp_formulation.to_string(bpp_data))

Bin Packing Problem Formulation:
  Items: 8
  Max bins: 8
  Bin capacity: 10.0

Decision Variables:
  x[i,j] in {0,1} for i = 0, ..., 7, j = 0, ..., 7
  x[i,j] = 1 if item i is packed in bin j
  y[j] in {0,1} for j = 0, ..., 7
  y[j] = 1 if bin j is used
  Total: 72 binary variables

Objective:
  minimize sum_j y[j]  for j = 0, ..., 7

Constraints:
  1. Each item in exactly one bin (8 constraints):
     sum_j x[i,j] == 1  for all i = 0, ..., 7
  2. Bin capacity not exceeded (8 constraints):
     sum_i w[i] * x[i,j] <= 10.0 * y[j]   for all j = 0, ..., 7

Create Instance

Combine data and formulation into an instance.

instance = BppInstance(data=bpp_data, formulation=bpp_formulation)
print(instance.to_string())

Data:Bin Packing Data:
  Items: 8
  Item names: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
  Item weights: [4.5 2.3 6.1 3.8 5.2 1.9 4.  2.7]
  Bin capacity: 10.0
  Max bins: 8
Formulation:Bin Packing Problem Formulation:
  Items: 8
  Max bins: 8
  Bin capacity: 10.0

Decision Variables:
  x[i,j] in {0,1} for i = 0, ..., 7, j = 0, ..., 7
  x[i,j] = 1 if item i is packed in bin j
  y[j] in {0,1} for j = 0, ..., 7
  y[j] = 1 if bin j is used
  Total: 72 binary variables

Objective:
  minimize sum_j y[j]  for j = 0, ..., 7

Constraints:
  1. Each item in exactly one bin (8 constraints):
     sum_j x[i,j] == 1  for all i = 0, ..., 7
  2. Bin capacity not exceeded (8 constraints):
     sum_i w[i] * x[i,j] <= 10.0 * y[j]   for all j = 0, ..., 7

Formulate Model

Create the 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')

2026-05-29 11:33:28 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:35 INFO     Sleeping for 10.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:46 INFO     Sleeping for 15.0 seconds. Waiting and checking a function in a loop.

Bin Packing Solution:
  Bins used: 4
  Valid: True
  Bin assignments: [['A', 'B', 'F'], ['C', 'D'], ['E', 'G'], ['H']]
  Bin loads: [8.7, 9.899999999999999, 9.2, 2.7]

Plot Solution

Visualize the optimal solution.

ax = uc_solution.plot(bpp_data)
plt.show()

png

Collections

Generate a benchmark collection of random instances for batch processing.

collection = BppCollection.from_random(
    min_num_items=5,
    max_num_items=8,
    bin_capacity=10.0,
    num_instances=2,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)

Model: bin_packing_problem<bin_packing_problem>
Minimize
  y_0 + y_1 + y_2 + y_3 + y_4
Subject To
  item_one_bin_0: 6 * x_0_0 + 6 * x_0_1 + 6 * x_0_2 + 6 * x_0_3 + 6 * x_0_4 == 6
  item_one_bin_1: 6 * x_1_0 + 6 * x_1_1 + 6 * x_1_2 + 6 * x_1_3 + 6 * x_1_4 == 6
  item_one_bin_2: 6 * x_2_0 + 6 * x_2_1 + 6 * x_2_2 + 6 * x_2_3 + 6 * x_2_4 == 6
  item_one_bin_3: 6 * x_3_0 + 6 * x_3_1 + 6 * x_3_2 + 6 * x_3_3 + 6 * x_3_4 == 6
  item_one_bin_4: 6 * x_4_0 + 6 * x_4_1 + 6 * x_4_2 + 6 * x_4_3 + 6 * x_4_4 == 6
  capacity_0: 13.200000000000001 * x_0_0 + 19.200000000000003 * x_1_0
    + 9 * x_2_0 + 46.2 * x_3_0 + 36.599999999999994 * x_4_0 - 60 * y_0 <= 0
  capacity_1: 13.200000000000001 * x_0_1 + 19.200000000000003 * x_1_1
    + 9 * x_2_1 + 46.2 * x_3_1 + 36.599999999999994 * x_4_1 - 60 * y_1 <= 0
  capacity_2: 13.200000000000001 * x_0_2 + 19.200000000000003 * x_1_2
    + 9 * x_2_2 + 46.2 * x_3_2 + 36.599999999999994 * x_4_2 - 60 * y_2 <= 0
  capacity_3: 13.200000000000001 * x_0_3 + 19.200000000000003 * x_1_3
    + 9 * x_2_3 + 46.2 * x_3_3 + 36.599999999999994 * x_4_3 - 60 * y_3 <= 0
  capacity_4: 13.200000000000001 * x_0_4 + 19.200000000000003 * x_1_4
    + 9 * x_2_4 + 46.2 * x_3_4 + 36.599999999999994 * x_4_4 - 60 * y_4 <= 0
Binary
  x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_2_0 x_2_1 x_2_2
  x_2_3 x_2_4 x_3_0 x_3_1 x_3_2 x_3_3 x_3_4 x_4_0 x_4_1 x_4_2 x_4_3 x_4_4 y_0
  y_1 y_2 y_3 y_4