Skip to content

Cutting Stock Problem (CSP) API Reference

Data

Data model for CuttingStock use case.

CuttingStockData

Bases: UcData

Data for the Cutting Stock Problem (CSP) use case.

This class encapsulates all necessary information to define and solve a Cutting Stock Problem instance. Given stock rolls of a fixed length and a set of desired piece lengths with associated demands, the CSP tries to cut all requested pieces from the minimum number of stock rolls.

Attributes:

  • name (Literal['cutting_stock']) –

    A constant identifier for this data type, always set to "cutting_stock". Used for registration and type identification in the use case registry.

  • roll_length (int) –

    The total length of each stock roll. Example: 100

  • desired_lengths (NumPyArray) –

    The length of each desired piece type as a 1D NumPy array of integers. Example: np.array([25, 30, 45])

  • demands (NumPyArray) –

    The number of pieces needed for each desired length as a 1D NumPy array of integers. Example: np.array([10, 5, 8])

Examples:

Create a simple cutting stock instance:

>>> csp = CuttingStockData(
...     name="cutting_stock",
...     roll_length=100,
...     desired_lengths=np.array([25, 30, 45]),
...     demands=np.array([10, 5, 8]),
... )

greedy_upper_bound: int cached property

Compute a safe upper bound on the number of rolls via greedy bin packing.

Repeats each piece length by its demand, sorts in ascending order, and greedily assigns pieces to rolls, opening a new roll whenever the current one is full.

Returns:

  • int –

    A guaranteed upper bound on the number of rolls needed.

plot(*, ax: Axes | None = None) -> Axes

Plot desired piece lengths with their demands.

Each row represents a piece type. The horizontal bar corresponds to the piece length, and the demand is shown as text on the right in the format "x ".

This representation is aligned with the solution plot, making it easier to visually compare input and output.

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(desired_lengths: np.ndarray, demands: np.ndarray, roll_length: int) -> CuttingStockData staticmethod

Create CuttingStockData from arrays.

Parameters:

  • desired_lengths (ndarray) –

    Array of desired piece lengths (integers).

  • demands (ndarray) –

    Array of demands for each piece length (integers).

  • roll_length (int) –

    Length of each stock roll.

Returns:

generate_random(n_types: int = 5, roll_length: int = 100, length_max: int | None = None, demand_max: int = 10, seed: int | None = None) -> CuttingStockData staticmethod

Generate a random Cutting Stock instance.

Parameters:

  • n_types (int, default: 5 ) –

    Number of distinct piece types, by default 5.

  • roll_length (int, default: 100 ) –

    Length of each stock roll, by default 100.

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

    Maximum piece length. If None, defaults to roll_length - 1.

  • demand_max (int, default: 10 ) –

    Maximum demand for each piece type, by default 10.

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

    Random seed for reproducibility, by default None.

Returns:

Formulation

Formulation for CuttingStock use case.

CuttingStockFormulation

Bases: UcFormulation[CuttingStockData, CuttingStockSolution]

Constraint-based formulation for the Cutting Stock Problem.

This formulation uses Luna Model's constraint system rather than manual QUBO penalty terms.

Mathematical Formulation

Given: - L: roll length - n: number of piece types - l_i: desired length of piece type i - d_i: demand for piece type i - M: upper bound on number of rolls (via greedy bin packing)

Decision Variables: x[i,j] integer >= 0 for each piece type i and roll j: number of pieces of type i cut from roll j y[j] in {0,1} for each roll j: 1 if roll j is used

Objective: minimize sum_j y[j] (minimize number of rolls used)

Constraints: 1. Demand satisfaction: For each piece type i: sum_j x[i,j] == d_i 2. Roll capacity: For each roll j: sum_i (l_i * x[i,j]) <= L * y[j] 3. Activation (linking): For each roll j: sum_i x[i,j] <= M_max * y[j]

References
  • Wikipedia: https://en.wikipedia.org/wiki/Cutting_stock_problem

to_string(data: CuttingStockData) -> str staticmethod

Print the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: CuttingStockData) -> Model staticmethod

Formulate the Cutting Stock Problem as a mixed-integer program.

This formulation models the assignment of pieces to rolls using integer variables representing how many pieces of each type are cut from each roll.

Decision Variables

x[i,j] : integer >= 0 Number of pieces of type i assigned to roll j. y[j] : binary Indicates whether roll j is used.

Objective

Minimize the number of rolls used: minimize sum_j y[j]

Constraints

  1. Demand satisfaction: For each piece type i: sum_j x[i,j] == d[i]

  2. Roll capacity: For each roll j: sum_i l[i] * x[i,j] <= L * y[j]

  3. Activation (linking constraint): Prevents unused rolls from being marked as active: sum_i x[i,j] <= M * y[j]

    where M is the maximum number of pieces that can fit into a roll.

Parameters:

  • data (CuttingStockData) –

    The problem instance containing roll length, piece lengths, and demands.

Returns:

  • Model –

    A Luna Model ready to be solved.

interpret(solution: Solution, data: CuttingStockData) -> CuttingStockSolution staticmethod

Extract solution from solver result.

Interprets integer decision variables x[i,j] as counts of pieces and reconstructs cutting patterns per used roll. Computes key metrics and validates feasibility.

Parameters:

  • solution (Solution) –

    The solution containing variable assignments.

  • data (CuttingStockData) –

    The original Cutting Stock instance data.

Returns:

  • CuttingStockSolution –

    A structured solution object with: - cutting_patterns: list of lists with piece lengths per roll - n_rolls_used: number of rolls used - total_waste: total unused length across all rolls - is_valid: whether the solution satisfies all constraints

Raises:

Solution

Solution model for CuttingStock use case.

CuttingStockSolution

Bases: UcSolution

Solution for the Cutting Stock Problem (CSP) use case.

This class represents a solution to a CSP instance, containing the cutting patterns for each roll used, the total number of rolls, total waste, and whether the solution is valid.

Attributes:

  • name (Literal['cutting_stock']) –

    A constant identifier for this solution type, always set to "cutting_stock".

  • cutting_patterns (list[list[int]]) –

    A list of rolls, where each roll is a list of cut piece lengths. Example: [[25, 25, 45], [30, 30, 25]] means roll 0 has pieces of lengths 25, 25, 45 and roll 1 has pieces of lengths 30, 30, 25.

  • n_rolls_used (int) –

    The total number of stock rolls used.

  • total_waste (int) –

    The total wasted material across all rolls.

  • is_valid (bool) –

    Whether all demands are satisfied and no roll exceeds roll_length.

Examples:

A valid solution:

>>> solution = CuttingStockSolution(
...     name="cutting_stock",
...     cutting_patterns=[[25, 25, 45], [30, 30, 25]],
...     n_rolls_used=2,
...     total_waste=20,
...     is_valid=True,
... )

plot(data: CuttingStockData | None = None, *, ax: Axes | None = None) -> Axes

Plot the cutting stock solution.

When data is provided the plot shows a stacked horizontal bar chart where each bar represents a roll and the segments represent the cut pieces, with waste shown in grey. Without data a simple bar chart of rolls used and total waste is drawn.

Parameters:

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

    Problem data. When provided, rolls are shown with piece segments.

  • 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 CuttingStock use case.

CuttingStockInstance

Bases: UcInstance[CuttingStockData, CuttingStockFormulation, CuttingStockSolution]

Instance combining data and formulation for CuttingStock.

Collection

Collection of CuttingStock instances.

CuttingStockCollection

Bases: UcInstanceCollection[CuttingStockInstance]

Collection of Cutting Stock Problem instances.

This collection provides methods to generate cutting stock instances with various characteristics for benchmarking and testing.

from_random(min_n_types: int, max_n_types: int, num_instances: int = 1, *, roll_length: int = 100, demand_max: int = 10, seed: int | None = None) -> CuttingStockCollection classmethod

Generate random cutting stock instances with varying numbers of piece types.

Parameters:

  • min_n_types (int) –

    Minimum number of piece types per instance.

  • max_n_types (int) –

    Maximum number of piece types per instance.

  • num_instances (int, default: 1 ) –

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

  • roll_length (int, default: 100 ) –

    Length of each stock roll, by default 100.

  • demand_max (int, default: 10 ) –

    Maximum demand for each piece type, by default 10.

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

    Random seed for reproducible results, by default None.

Returns:

Examples:

>>> collection = CuttingStockCollection.from_random(
...     min_n_types=3,
...     max_n_types=6,
...     num_instances=2,
...     seed=42,
... )

from_tight_capacity(min_n_types: int, max_n_types: int, num_instances: int = 1, *, roll_length: int = 100, capacity_ratio: float = 0.85, seed: int | None = None) -> CuttingStockCollection classmethod

Generate tight-capacity cutting stock instances.

Creates harder instances where the total demanded material is close to the theoretical minimum number of rolls times the roll length, meaning there is little room for waste. Piece lengths are chosen to be relatively large compared to the roll length.

Parameters:

  • min_n_types (int) –

    Minimum number of piece types per instance.

  • max_n_types (int) –

    Maximum number of piece types per instance.

  • num_instances (int, default: 1 ) –

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

  • roll_length (int, default: 100 ) –

    Length of each stock roll, by default 100.

  • capacity_ratio (float, default: 0.85 ) –

    Minimum ratio of piece length to roll length, by default 0.85. Higher values produce tighter (harder) instances.

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

    Random seed for reproducible results, by default None.

Returns:

Examples:

>>> collection = CuttingStockCollection.from_tight_capacity(
...     min_n_types=3,
...     max_n_types=6,
...     capacity_ratio=0.9,
...     seed=42,
... )