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	Type	Description
`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:

Type	Description
`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:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`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:

Name	Type	Description	Default
`desired_lengths`	`ndarray`	Array of desired piece lengths (integers).	required
`demands`	`ndarray`	Array of demands for each piece length (integers).	required
`roll_length`	`int`	Length of each stock roll.	required

Returns:

Type	Description
`CuttingStockData`	The created CuttingStock data instance.

`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:

Name	Type	Description	Default
`n_types`	`int`	Number of distinct piece types, by default 5.	`5`
`roll_length`	`int`	Length of each stock roll, by default 100.	`100`
`length_max`	`int \| None`	Maximum piece length. If None, defaults to roll_length - 1.	`None`
`demand_max`	`int`	Maximum demand for each piece type, by default 10.	`10`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`CuttingStockData`	A randomly generated Cutting Stock data instance.

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:

Name	Type	Description	Default
`data`	`CuttingStockData`	The problem data.	required

Returns:

Type	Description
`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

Demand satisfaction: For each piece type i: sum_j x[i,j] == d[i]
Roll capacity: For each roll j: sum_i l[i] * x[i,j] <= L * y[j]
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:

Name	Type	Description	Default
`data`	`CuttingStockData`	The problem instance containing roll length, piece lengths, and demands.	required

Returns:

Type	Description
`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:

Name	Type	Description	Default
`solution`	`Solution`	The solution containing variable assignments.	required
`data`	`CuttingStockData`	The original Cutting Stock instance data.	required

Returns:

Type	Description
`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:

Type	Description
`NoSolutionFoundError`	If the solver did not find a solution.

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	Type	Description
`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:

Name	Type	Description	Default
`data`	`CuttingStockData \| None`	Problem data. When provided, rolls are shown with piece segments.	`None`
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`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:

Name	Type	Description	Default
`min_n_types`	`int`	Minimum number of piece types per instance.	required
`max_n_types`	`int`	Maximum number of piece types per instance.	required
`num_instances`	`int`	Number of instances to generate for each piece type count, by default 1.	`1`
`roll_length`	`int`	Length of each stock roll, by default 100.	`100`
`demand_max`	`int`	Maximum demand for each piece type, by default 10.	`10`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`CuttingStockCollection`	Collection containing generated Cutting Stock instances.

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:

Name	Type	Description	Default
`min_n_types`	`int`	Minimum number of piece types per instance.	required
`max_n_types`	`int`	Maximum number of piece types per instance.	required
`num_instances`	`int`	Number of instances to generate for each piece type count, by default 1.	`1`
`roll_length`	`int`	Length of each stock roll, by default 100.	`100`
`capacity_ratio`	`float`	Minimum ratio of piece length to roll length, by default 0.85. Higher values produce tighter (harder) instances.	`0.85`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`CuttingStockCollection`	Collection containing generated tight-capacity instances.

Examples:

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

Cutting Stock Problem (CSP) API Reference

Data

CuttingStockData

greedy_upper_bound: int cached property

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

to_string() -> str

from_arrays(desired_lengths: np.ndarray, demands: np.ndarray, roll_length: int) -> CuttingStockData staticmethod

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

Formulation

CuttingStockFormulation

to_string(data: CuttingStockData) -> str staticmethod

formulate(data: CuttingStockData) -> Model staticmethod

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

Solution

CuttingStockSolution

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

to_string() -> str

Instance

CuttingStockInstance

Collection

CuttingStockCollection

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

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

`CuttingStockData`

`greedy_upper_bound: int` `cached` `property`

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

`to_string() -> str`

`from_arrays(desired_lengths: np.ndarray, demands: np.ndarray, roll_length: int) -> CuttingStockData` `staticmethod`

`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`

`CuttingStockFormulation`

`to_string(data: CuttingStockData) -> str` `staticmethod`

`formulate(data: CuttingStockData) -> Model` `staticmethod`

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

`CuttingStockSolution`

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

`to_string() -> str`

`CuttingStockInstance`

`CuttingStockCollection`

`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`

`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`