Cutting Stock Example
The Cutting Stock Problem is a classic combinatorial optimization problem: given stock rolls of a fixed length and a set of desired piece lengths with associated demands, determine how to cut all requested pieces from the minimum number of stock rolls.
import getpass
import os
import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP
from luna_usecases.cutting_stock import (
CuttingStockCollection,
CuttingStockData,
CuttingStockFormulation,
CuttingStockInstance,
)
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 cutting stock instance with 3 piece types using the from_arrays() factory method. The stock roll has length 100, and we need pieces of lengths 25, 30, and 45 in various quantities.
desired_lengths = np.array([25, 30, 45])
demands = np.array([4, 3, 2])
roll_length = 100
data = CuttingStockData.from_arrays(
desired_lengths=desired_lengths,
demands=demands,
roll_length=roll_length,
)
print(data.to_string())
Cutting Stock Problem:
Roll length: 100
Number of piece types: 3
Desired lengths: [25 30 45]
Demands: [4 3 2]
Plot Data
Visualize desired piece lengths and their demands.
Create Formulation
Minimize the number of stock rolls used while satisfying all piece demands and respecting roll capacity.
Cutting Stock Problem Formulation:
Piece types: 3
Roll length: 100
Max rolls (upper bound): 3
Decision Variables:
x[i,j] integer >= 0 for i = 0, ..., 2, j = 0, ..., 2
x[i,j] = number of pieces of type i cut from roll j
y[j] in {0,1} for j = 0, ..., 2
y[j] = 1 if roll j is used
Total: 12 variables
Objective:
minimize sum_j y[j] for j = 0, ..., 2
Constraints:
1. Demand satisfaction (3 constraints):
sum_j x[i,j] == d[i] for all i = 0, ..., 2
2. Roll capacity (3 constraints):
sum_i (l[i] * x[i,j]) <= 100 * y[j] for all j = 0, ..., 2
3. Activation (3 constraints):
sum_i x[i,j] <= M * y[j] for all j = 0, ..., 2
Create Instance
Combine data and formulation into a solvable instance.
Data:Cutting Stock Problem:
Roll length: 100
Number of piece types: 3
Desired lengths: [25 30 45]
Demands: [4 3 2]
Formulation:Cutting Stock Problem Formulation:
Piece types: 3
Roll length: 100
Max rolls (upper bound): 3
Decision Variables:
x[i,j] integer >= 0 for i = 0, ..., 2, j = 0, ..., 2
x[i,j] = number of pieces of type i cut from roll j
y[j] in {0,1} for j = 0, ..., 2
y[j] = 1 if roll j is used
Total: 12 variables
Objective:
minimize sum_j y[j] for j = 0, ..., 2
Constraints:
1. Demand satisfaction (3 constraints):
sum_j x[i,j] == d[i] for all i = 0, ..., 2
2. Roll capacity (3 constraints):
sum_i (l[i] * x[i,j]) <= 100 * y[j] for all j = 0, ..., 2
3. Activation (3 constraints):
sum_i x[i,j] <= M * y[j] for all j = 0, ..., 2
Formulate Model
Translate the instance into a mathematical optimization model.
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:33 INFO Sleeping for 5.0 seconds. Waiting and checking a function in a loop.
2026-05-29 11:33:40 INFO Sleeping for 10.0 seconds. Waiting and checking a function in a loop.
2026-05-29 11:33:51 INFO Sleeping for 15.0 seconds. Waiting and checking a function in a loop.
2026-05-29 11:34:07 INFO Sleeping for 20.0 seconds. Waiting and checking a function in a loop.
Cutting Stock Problem Solution:
Number of rolls used: 3
Total waste: 20
Is valid: True
Roll 0: [25, 25, 25, 25] (sum=100)
Roll 1: [30, 30, 30] (sum=90)
Roll 2: [45, 45] (sum=90)
Plot Solution
Visualize the cutting patterns across rolls.
Collections
Generate benchmark collections of cutting stock instances for batch processing.
collection = CuttingStockCollection.from_random(
min_n_types=3,
max_n_types=5,
num_instances=2,
roll_length=100,
seed=42,
)
model = collection.instances[0].formulate()
print(model)
Model: cutting_stock<cutting_stock>
Minimize
y_0 + y_1 + y_2 + y_3 + y_4 + y_5 + y_6 + y_7 + y_8 + y_9 + y_10 + y_11 + y_12
+ y_13 + y_14
Subject To
demand_0: x_0_0 + x_0_1 + x_0_2 + x_0_3 + x_0_4 + x_0_5 + x_0_6 + x_0_7
+ x_0_8 + x_0_9 + x_0_10 + x_0_11 + x_0_12 + x_0_13 + x_0_14 == 5
demand_1: x_1_0 + x_1_1 + x_1_2 + x_1_3 + x_1_4 + x_1_5 + x_1_6 + x_1_7
+ x_1_8 + x_1_9 + x_1_10 + x_1_11 + x_1_12 + x_1_13 + x_1_14 == 5
demand_2: x_2_0 + x_2_1 + x_2_2 + x_2_3 + x_2_4 + x_2_5 + x_2_6 + x_2_7
+ x_2_8 + x_2_9 + x_2_10 + x_2_11 + x_2_12 + x_2_13 + x_2_14 == 9
capacity_0: 9 * x_0_0 + 77 * x_1_0 + 65 * x_2_0 - 100 * y_0 <= 0
capacity_1: 9 * x_0_1 + 77 * x_1_1 + 65 * x_2_1 - 100 * y_1 <= 0
capacity_2: 9 * x_0_2 + 77 * x_1_2 + 65 * x_2_2 - 100 * y_2 <= 0
capacity_3: 9 * x_0_3 + 77 * x_1_3 + 65 * x_2_3 - 100 * y_3 <= 0
capacity_4: 9 * x_0_4 + 77 * x_1_4 + 65 * x_2_4 - 100 * y_4 <= 0
capacity_5: 9 * x_0_5 + 77 * x_1_5 + 65 * x_2_5 - 100 * y_5 <= 0
capacity_6: 9 * x_0_6 + 77 * x_1_6 + 65 * x_2_6 - 100 * y_6 <= 0
capacity_7: 9 * x_0_7 + 77 * x_1_7 + 65 * x_2_7 - 100 * y_7 <= 0
capacity_8: 9 * x_0_8 + 77 * x_1_8 + 65 * x_2_8 - 100 * y_8 <= 0
capacity_9: 9 * x_0_9 + 77 * x_1_9 + 65 * x_2_9 - 100 * y_9 <= 0
capacity_10: 9 * x_0_10 + 77 * x_1_10 + 65 * x_2_10 - 100 * y_10 <= 0
capacity_11: 9 * x_0_11 + 77 * x_1_11 + 65 * x_2_11 - 100 * y_11 <= 0
capacity_12: 9 * x_0_12 + 77 * x_1_12 + 65 * x_2_12 - 100 * y_12 <= 0
capacity_13: 9 * x_0_13 + 77 * x_1_13 + 65 * x_2_13 - 100 * y_13 <= 0
capacity_14: 9 * x_0_14 + 77 * x_1_14 + 65 * x_2_14 - 100 * y_14 <= 0
activation_0: x_0_0 + x_1_0 + x_2_0 - 11 * y_0 <= 0
activation_1: x_0_1 + x_1_1 + x_2_1 - 11 * y_1 <= 0
activation_2: x_0_2 + x_1_2 + x_2_2 - 11 * y_2 <= 0
activation_3: x_0_3 + x_1_3 + x_2_3 - 11 * y_3 <= 0
activation_4: x_0_4 + x_1_4 + x_2_4 - 11 * y_4 <= 0
activation_5: x_0_5 + x_1_5 + x_2_5 - 11 * y_5 <= 0
activation_6: x_0_6 + x_1_6 + x_2_6 - 11 * y_6 <= 0
activation_7: x_0_7 + x_1_7 + x_2_7 - 11 * y_7 <= 0
activation_8: x_0_8 + x_1_8 + x_2_8 - 11 * y_8 <= 0
activation_9: x_0_9 + x_1_9 + x_2_9 - 11 * y_9 <= 0
activation_10: x_0_10 + x_1_10 + x_2_10 - 11 * y_10 <= 0
activation_11: x_0_11 + x_1_11 + x_2_11 - 11 * y_11 <= 0
activation_12: x_0_12 + x_1_12 + x_2_12 - 11 * y_12 <= 0
activation_13: x_0_13 + x_1_13 + x_2_13 - 11 * y_13 <= 0
activation_14: x_0_14 + x_1_14 + x_2_14 - 11 * y_14 <= 0
Bounds
0 <= x_0_0 <= 11
0 <= x_0_1 <= 11
0 <= x_0_2 <= 11
0 <= x_0_3 <= 11
0 <= x_0_4 <= 11
0 <= x_0_5 <= 11
0 <= x_0_6 <= 11
0 <= x_0_7 <= 11
0 <= x_0_8 <= 11
0 <= x_0_9 <= 11
0 <= x_0_10 <= 11
0 <= x_0_11 <= 11
0 <= x_0_12 <= 11
0 <= x_0_13 <= 11
0 <= x_0_14 <= 11
0 <= x_1_0 <= 1
0 <= x_1_1 <= 1
0 <= x_1_2 <= 1
0 <= x_1_3 <= 1
0 <= x_1_4 <= 1
0 <= x_1_5 <= 1
0 <= x_1_6 <= 1
0 <= x_1_7 <= 1
0 <= x_1_8 <= 1
0 <= x_1_9 <= 1
0 <= x_1_10 <= 1
0 <= x_1_11 <= 1
0 <= x_1_12 <= 1
0 <= x_1_13 <= 1
0 <= x_1_14 <= 1
0 <= x_2_0 <= 1
0 <= x_2_1 <= 1
0 <= x_2_2 <= 1
0 <= x_2_3 <= 1
0 <= x_2_4 <= 1
0 <= x_2_5 <= 1
0 <= x_2_6 <= 1
0 <= x_2_7 <= 1
0 <= x_2_8 <= 1
0 <= x_2_9 <= 1
0 <= x_2_10 <= 1
0 <= x_2_11 <= 1
0 <= x_2_12 <= 1
0 <= x_2_13 <= 1
0 <= x_2_14 <= 1
Binary
y_0 y_1 y_2 y_3 y_4 y_5 y_6 y_7 y_8 y_9 y_10 y_11 y_12 y_13 y_14
Integer
x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_0_5 x_0_6 x_0_7 x_0_8 x_0_9 x_0_10 x_0_11
x_0_12 x_0_13 x_0_14 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_1_5 x_1_6 x_1_7 x_1_8
x_1_9 x_1_10 x_1_11 x_1_12 x_1_13 x_1_14 x_2_0 x_2_1 x_2_2 x_2_3 x_2_4 x_2_5
x_2_6 x_2_7 x_2_8 x_2_9 x_2_10 x_2_11 x_2_12 x_2_13 x_2_14