Formulating Multistage Cutting Stock Problems as QUBO

AI summary

Overview

Research area: Quantum computing for optimization — specifically, mapping an industrial cutting-stock problem onto a Quadratic Unconstrained Binary Optimization (QUBO) formulation suitable for quantum annealing hardware.

Technical level: Advanced. The paper assumes familiarity with integer linear programming, penalty methods, QUBO/Hamiltonian formulations, and quantum annealing.

Scope: The paper derives a 0-1 integer linear programming formulation and a corresponding QUBO formulation of the restricted multistage 2D cutting stock problem with Guillotine cuts, tests the linear formulation on published benchmarks, and studies solution strategies (primarily an iterative augmented Lagrangian method with a Simulated Annealing sampler) plus quantum annealing hardware considerations.

What This Paper Is About

Cutting stock problems ask how to cut rectangular pieces of required sizes out of larger plates as efficiently as possible, and are central to industries working with plywood, paper, metal plates, and glass sheets. Because real cutting machines usually require Guillotine cuts (cuts that run all the way through the material), and because quantum annealers can only natively handle QUBO form, the authors need a way to express the "multistage" Guillotine cutting problem as a QUBO without the usual slack-variable overhead. The paper's goal is to build that formulation, show how it can also favor large reusable leftover pieces, and study how such QUBOs behave when attacked with Simulated Annealing and, in principle, quantum annealing.

Key Contributions

1. A 0-1 integer linear programming formulation of the restricted multistage 2D cutting stock problem with Guillotine cuts, built as a tree structure over required pieces using binary neighbor variables, with size constraints, demand constraints, and an extension for rotated pieces. This formulation is tested on published benchmark instances.

2. A non-exact QUBO reformulation via unbalanced penalization that handles the problem's inequality constraints without introducing slack variables. The demand inequality is handled by a quadratic term (described as Transformation #2 in the cited literature), while the size inequalities use the unbalanced penalization method.

3. Explicit variable-count formulas for the QUBO, including a general count of 2(m̃+P+1)² − 2(m̃+P+1) for m̃ required pieces (m̃ = 2m if rotation is allowed, otherwise m̃ = m) and P plates, reduced to 2m̃² − m̃ + 1 by fixing starting-node variables.

4. A treatment of "usable leftovers" — showing how additional quadratic objective terms can push solutions toward cutting patterns whose waste pieces are large rather than fragmented, and connecting this to hyperparameter choices in the size penalty.

5. An augmented Lagrangian algorithm for solving the QUBO iteratively, with Lagrange multiplier updates, and a demonstration that the augmented Lagrangian formulation is a special case of the general penalized QUBO with λ_quad = 0, λ_size = μ, and λ_unb = λ/μ.

Main Findings

• Slack variables can be avoided for the demand constraint. The demand inequality is enforced by a term of the form λ[(Σ_j(x_{j,k}+y_{j,k}))(Σ_j(x_{j,k}+y_{j,k})) − Σ_j(x_{j,k}² + y_{j,k}²)], which the authors note avoids the "significant additional overhead" that slack variables typically incur.

• Unbalanced penalization effectively shrinks the parent piece. Rewriting the size penalty (ξ² − λ_unb ξ) as a shifted square shows the linear term behaves like an increase of the piece length l_i by λ_unb/2, or equivalently like shrinking the ancestor piece by a fixed length.

• Large λ_unb destroys the incentive to place pieces. When the objective term equals the piece areas, increasing unbalanced penalization is mathematically equivalent to decreasing the value of the parts. The authors therefore suggest the bound λ_unb ≤ min{l_1,…,l_N, w_1,…,w_N} / λ_size (Equation 23) as a starting point for hyperparameter tuning.

• Waste-area minimization alone is insufficient for usable leftovers. The authors argue that a purely linear waste term A_rest, and even the dimension-weighted version A_weighted, cannot reliably prevent unnecessary cutting-down of rest pieces, because the effect of a single variable x_{i,j} on leftover usability depends on the values of other variables. They propose quadratic terms A_quad instead.

• Quadratic leftover terms change the effective penalty. Combining the size penalty with the quadratic leftover term yields per-piece quadratic coefficients of the form (λ_size − λ_quad w_i²) and (λ_size − λ_quad l_i²), showing that leftover preference and constraint enforcement are coupled through the same hyperparameters.

• Toy example shows λ_unb controls the cutting pattern. For N = 30 squares of size 200 cut from a plate, λ_unb = 0 produces an infeasible plan in which the pieces slightly exceed the plate width, whereas nonzero λ_unb effectively decreases L and W and moves the optimum to an intermediate configuration (Figure 2). The authors state that no single λ_unb is likely optimal for all settings.

• Augmented Lagrangian is the main numerical focus. The paper states that the numerical experiments mainly use augmented Lagrangian methods, which can be interpreted as iteratively optimizing the free parameters of the unbalanced penalization formulation, with a Simulated Annealing solver generating candidate samples.

• Numerical benchmark results are not reported in the available text. The paper states that benchmark instances from a published source are considered and compared against that source's optimal solution, but the specific solution values, gaps, instance names, and run times appear in Section IV, which is not included in the supplied content.

• Scaling and annealing dynamics are analyzed in separate sections. Section V is described as a scaling analysis and Section VI as an analysis of representative QUBO instances through quantum annealing simulations; their specific results are not included in the supplied content.

Methodology in Plain English

The authors first describe the cutting plan as a tree. Each required piece is a node, and a node's children are the pieces cut out of the same intermediate piece in a later cutting stage. Cuts alternate between horizontal and vertical direction, which is what "multistage" means. Two special starting nodes represent the plate itself, and binary variables record whether one piece sits horizontally or vertically next to another. Constraints ensure each required piece appears at most once, and that pieces never exceed the intermediate piece they are cut from. Because the problem is "restricted," every cut has the dimensions of one required piece, which keeps the model linear. Rotated copies of pieces can be added as extra indices.

To turn this into a QUBO, the demand constraint is converted into a quadratic penalty without slack variables. The size constraints, which are inequalities, are converted with unbalanced penalization: instead of penalizing the squared violation, the authors penalize ξ² − λ_unb ξ, which approximates an exponential energy that rises steeply for infeasible values but is mildly favorable for small positive slack. This is an approximation, so the QUBO is explicitly described as non-exact.

Rather than hand-tuning λ_unb, the main numerical approach is an augmented Lagrangian loop: solve a QUBO, measure the constraint violations, update the Lagrange multipliers, rebuild the QUBO, and repeat. The algorithm keeps the best feasible solution found. Because a sampler returns a histogram of many candidate solutions, the authors suggest picking the best feasible candidate from the histogram rather than only the lowest-energy sample.

The paper also reviews the MAGIC trapped-ion architecture as a possible hardware platform. There, qubits are encoded in ¹⁷¹Yb⁺ states, a magnetic field gradient gives each ion a unique addressing frequency, and the resulting position-dependent Coulomb interaction produces an always-on all-to-all coupling. Arbitrary effective couplings are obtained through gate synthesis (repeated bit flips and waiting times), which naturally leads to a trotterized annealing schedule.

Why This Matters

Impact on research. Cutting stock problems are traditionally solved with mixed-integer linear programming, branch and bound, dynamic programming, or heuristics. This paper shows a concrete route from an industrially standard ILP model to a QUBO that avoids slack variables, and it highlights that QUBO formulations offer modeling freedom (extra quadratic objective terms) that linear programs do not easily provide. It also gives a template for combining augmented Lagrangian methods with stochastic QUBO samplers, building on prior work on bin packing.

Real-world applications:

• Cutting plywood or wood panels in furniture and construction manufacturing.
• Cutting paper rolls and sheets in printing and packaging.
• Cutting metal plates in fabrication and shipbuilding.
• Cutting glass sheets in window and display production.

Industry relevance. Guillotine cutting is a hard technological constraint on real machines, and alternating cut directions across stages reflects how those machines actually operate. Any approach that reduces material waste, or that produces leftover pieces large enough to be stored and reused, translates directly into cost savings. The paper's explicit attention to usable leftovers — including whether waste is fragmented during cutting — addresses a practical concern that standard waste-area objectives miss.

Future Directions

• Extending from the restricted to the unrestricted problem. The authors note that allowing cuts with dimensions of multiple required pieces naturally produces quadratic terms in the problem's inequalities, which the current formulation does not handle.

• Experimental demonstration on quantum hardware. The MAGIC trapped-ion architecture is presented as a reference platform on which the proposed QUBO approach "could, in principle, be implemented experimentally," but no hardware results are reported in the available content.

• Systematic hyperparameter tuning. The paper shows that λ_unb, λ_size, and λ_quad strongly influence solution quality and are coupled; it provides bounds and a starting-point heuristic but states that no single λ_unb is likely optimal across settings.

• Comparing solvers and scales. The scaling analysis and quantum annealing simulations promised in Sections V and VI raise the open question of how large an instance current and near-term annealers can handle, and how their solution quality compares with the classical ILP benchmarks.

Target Audience

Researchers and practitioners working at the intersection of quantum optimization and operations research — particularly those interested in QUBO formulations of constrained combinatorial problems, penalty and augmented Lagrangian methods for quantum annealers and samplers, and industrial cutting and packing applications. It is also relevant to quantum hardware developers evaluating application-relevant problem classes for trapped-ion or superconducting annealing platforms. Readers without a background in integer programming or QUBO penalty methods will find the formulation sections demanding.

Authors’ 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.