Formulating Multistage Cutting Stock Problems as QUBO
Abstract
Cutting stock problems are of large relevance to a variety of industry branches. Here, we present a linear programming formulation for a restricted version of the multistage 2D cutting stock problem with Guillotine cuts and test it on published benchmark instances. After this, we derive a non-exact reformulation in quadratic unconstrained binary optimization (QUBO) form via unbalanced penalization, which we show to have possible benefits in modeling the problem with usable leftovers. This work mainly considers the restricted formulation, in which the dimensions of each cut are determined by those of a single required piece. We further discuss how the approach can be extended to the unrestricted problem, which allows more general cutting patterns involving cuts with dimensions of multiple required pieces and naturally gives rise to quadratic terms in the inequalities of the problem formulation. We showcase solutions via a Simulated Annealing solver for the restricted problem class, where we mainly study the performance of the iterative augmented Lagrangian method. We also discuss possible applications of Quantum Annealing in this setting, as a strong motivation to research QUBO formulations.
Related
- A large neighborhood search matheuristic for the two-dimensional guillotine flexible stock size cutting stock problem
- Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware
- A variational quantum eigensolver-based cutting plane framework for semidefinite programming problems
- Stock Exchange Trading Optimization Algorithm Improved Based on Information Technology Investment Analysis for Numerical Optimization and Practical Problems
- Formulating Cross-World Mediation Estimands Through Single-World Mixtures
BibTeX
@misc{benkner2026formulating,
title = {{Formulating Multistage Cutting Stock Problems as QUBO}},
author = {Marcel Seelbach Benkner and Chiara Capecci and Sebastian Nagies and Javed Akram and Sebastian Rubbert and Dimitrios Bantounas and Philipp Hauke and Michael Johanning and Michael Moeller},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14070},
eprint = {2609.14070},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14070},
}
RIS
TY - UNPB
TI - Formulating Multistage Cutting Stock Problems as QUBO
AU - Marcel Seelbach Benkner
AU - Chiara Capecci
AU - Sebastian Nagies
AU - Javed Akram
AU - Sebastian Rubbert
AU - Dimitrios Bantounas
AU - Philipp Hauke
AU - Michael Johanning
AU - Michael Moeller
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.14070
UR - https://arxiv.org/abs/2609.14070
AB - Cutting stock problems are of large relevance to a variety of industry branches. Here, we present a linear programming formulation for a restricted version of the multistage 2D cutting stock problem with Guillotine cuts and test it on published benchmark instances. After this, we derive a non-exact reformulation in quadratic unconstrained binary optimization (QUBO) form via unbalanced penalization, which we show to have possible benefits in modeling the problem with usable leftovers. This work mainly considers the restricted formulation, in which the dimensions of each cut are determined by those of a single required piece. We further discuss how the approach can be extended to the unrestricted problem, which allows more general cutting patterns involving cuts with dimensions of multiple required pieces and naturally gives rise to quadratic terms in the inequalities of the problem formulation. We showcase solutions via a Simulated Annealing solver for the restricted problem class, where we mainly study the performance of the iterative augmented Lagrangian method. We also discuss possible applications of Quantum Annealing in this setting, as a strong motivation to research QUBO formulations.
ER -