Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.20853

Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware

Miguel Sánchez-Beato, Raul Martinez, Matilde Osa, Jorge Parra, Mario Calonge

quant-phmath.OCSubmitted Aug 26, 2026• Announced Aug 27, 2026• 0 citations
arXivHTMLPDF

Abstract

The two-dimensional Cutting Stock Problem (2D-CSP) is an NP-hard problem with direct economic and environmental impacts on manufacturing and logistics. We encode its fixed-plate variant, with free piece repetition and full non-overlap and containment constraints, as a Quadratic Unconstrained Binary Optimization (QUBO) problem for quantum annealing and compare two formulations from opposite encoding paradigms. The first was a coordinate-based set-packing model with one binary variable per candidate placement. Its variable count grows linearly with plate area and resolution, but its ground state is, by construction, a geometrically feasible maximum-area packing. The second is a coordinate-free sequence-pair model whose variable count is independent of plate resolution and size. We prove that this compactness has a structural limit: no coordinate-free QUBO of bounded interaction degree whose penalties vanish on every geometrically feasible layout can have a geometrically feasible ground state for 2D containment, because containment is a longest-path constraint that bounded-degree penalties cannot enforce on chains longer than their interaction order. We evaluate both formulations under multi-seed simulated annealing, simulated quantum annealing, and an exact integer-programming baseline. Hardware experiments include D-Wave minor embedding, a calibrated direct-QPU sweep, and Leap hybrid solvers in both penalty and constraint-native form, across a six-instance campaign with per-instance calibration. The hybrid solver returns our certificate configuration, tying its energy to thirteen decimal places while overflowing the plate. We claim no quantum speedup. Our contribution is an impossibility result characterizing the limits of compact packing QUBOs, and a practical rule for choosing between the two formulations.

Comments
15 pages, 4 figures, 6 tables. To be published in IEEE

Related papers

QUBO Formulation Using Sequence Pair With Search Space Restriction for Rectangle Packing Problem

A. Okada, Keisuke Otaki, Tadayoshi MATSUMORI +3 more

The development of quantum annealing has stimulated interest in solving NP-hard problems, including various industrial problems, such as quadratic unconstrained binary optimization (QUBO), with specialized solvers. This study focuses on the rectangle packing problem (RPP), which is an NP-hard problem applicable to industrial applications. The objective of this problem is to place given items in a minimum area without overlap. Naive QUBO representations, such as a direct binary encoding of locations, could require a large number of bits, which limits the problem size, hindering the acquisition of the optimal solution. To circumvent this difficulty, we employ the concept of sequence pairs to efficiently represent the locations of items. We also propose a strategy that uses multiple sampling solutions obtained with a QUBO solver, where we employ new constraints on the number of the rectangles contributing to the placement area for restricting the search space to smoothly bridge the QUBO formulation of the sequence pair and the minimization of area of rectangle placement. We estimate an approximate curve for the optimum number of rectangles contributing to the placement area. Then, we add the penalty term concerning the deviation from the estimated optimal value on the objective function. In numerical experiments with instances with 4 to 10 rectangles, we demonstrate that the proposed sampling-based strategy can efficiently find feasible solutions. This strategy would be useful for dealing with more complex problems, such as rectangle orientation and three-dimensional problems, with a relatively small number of bits using sequence pairs.

IEEE Access•Jan 1, 2024•1 citation

Formulating Multistage Cutting Stock Problems as QUBO

Marcel Seelbach Benkner, Chiara Capecci, Sebastian Nagies +6 more

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.

quant-pharXiv:2609.14070•Sep 15, 2026•0 citations

QUBO Formulation of the Pickup and Delivery Problem with Time Windows for Quantum Annealing

Cosmin Ștefan Curuliuc, Florin Leon

This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).

Applied Sciences•Feb 8, 2026•0 citations

Formulations for Quantum Annealed Project Scheduling

U Kanade

Resource constrained project scheduling and related allocation tasks can be expressed as Quadratic Unconstrained Binary Optimization (QUBO) models and submitted to quantum annealers. This paper develops the QUBO formulation in detail: choice of binary variables, linear and quadratic objective terms, conversion of precedence and resource constraints into penalty functions, and calibration of penalty weights. The resulting Hamiltonian is embedded onto quantum hardware, annealed, and post-processed. Hybrid classical–quantum workflows that wrap the QUBO solver inside Monte Carlo risk analysis or a digital twin are examined. Supporting process flowcharts and energy-landscape figures illustrate every stage. The treatment remains grounded in construction and logistics applications while remaining transferable to other combinatorial domains such as ULD configuration. Keywords: QUBO formulation; quantum annealing; Ising model; penalty methods; resource-constrained project scheduling; hybrid quantum-classical; minor embedding; Monte Carlo; digital twin.

International Journal of Creative and Open Research in Engineering and Management•Aug 22, 2026•0 citations

Constraint Embedding for Solving Optimization Problems on Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2019•2 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific Reports•Apr 6, 2023•10 citations
The two-dimensional Cutting Stock Problem (2D-CSP) is an NP-hard problem with direct economic and environmental impacts on manufacturing and logistics. We encode its fixed-plate variant, with free piece repetition and full non-overlap and containment constraints, as a Quadratic Unconstrained Binary Optimization (QUBO) problem for quantum annealing and compare two formulations from opposite encoding paradigms. The first was a coordinate-based set-packing model with one binary variable per candidate placement. Its variable count grows linearly with plate area and resolution, but its ground state is, by construction, a geometrically feasible maximum-area packing. The second is a coordinate-free sequence-pair model whose variable count is independent of plate resolution and size. We prove that this compactness has a structural limit: no coordinate-free QUBO of bounded interaction degree whose penalties vanish on every geometrically feasible layout can have a geometrically feasible ground state for 2D containment, because containment is a longest-path constraint that bounded-degree penalties cannot enforce on chains longer than their interaction order. We evaluate both formulations under multi-seed simulated annealing, simulated quantum annealing, and an exact integer-programming baseline. Hardware experiments include D-Wave minor embedding, a calibrated direct-QPU sweep, and Leap hybrid solvers in both penalty and constraint-native form, across a six-instance campaign with per-instance calibration. The hybrid solver returns our certificate configuration, tying its energy to thirteen decimal places while overflowing the plate. We claim no quantum speedup. Our contribution is an impossibility result characterizing the limits of compact packing QUBOs, and a practical rule for choosing between the two formulations.
The development of quantum annealing has stimulated interest in solving NP-hard problems, including various industrial problems, such as quadratic unconstrained binary optimization (QUBO), with specialized solvers. This study focuses on the rectangle packing problem (RPP), which is an NP-hard problem applicable to industrial applications. The objective of this problem is to place given items in a minimum area without overlap. Naive QUBO representations, such as a direct binary encoding of locations, could require a large number of bits, which limits the problem size, hindering the acquisition of the optimal solution. To circumvent this difficulty, we employ the concept of sequence pairs to efficiently represent the locations of items. We also propose a strategy that uses multiple sampling solutions obtained with a QUBO solver, where we employ new constraints on the number of the rectangles contributing to the placement area for restricting the search space to smoothly bridge the QUBO formulation of the sequence pair and the minimization of area of rectangle placement. We estimate an approximate curve for the optimum number of rectangles contributing to the placement area. Then, we add the penalty term concerning the deviation from the estimated optimal value on the objective function. In numerical experiments with instances with 4 to 10 rectangles, we demonstrate that the proposed sampling-based strategy can efficiently find feasible solutions. This strategy would be useful for dealing with more complex problems, such as rectangle orientation and three-dimensional problems, with a relatively small number of bits using sequence pairs.
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.
This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).
Resource constrained project scheduling and related allocation tasks can be expressed as Quadratic Unconstrained Binary Optimization (QUBO) models and submitted to quantum annealers. This paper develops the QUBO formulation in detail: choice of binary variables, linear and quadratic objective terms, conversion of precedence and resource constraints into penalty functions, and calibration of penalty weights. The resulting Hamiltonian is embedded onto quantum hardware, annealed, and post-processed. Hybrid classical–quantum workflows that wrap the QUBO solver inside Monte Carlo risk analysis or a digital twin are examined. Supporting process flowcharts and energy-landscape figures illustrate every stage. The treatment remains grounded in construction and logistics applications while remaining transferable to other combinatorial domains such as ULD configuration. Keywords: QUBO formulation; quantum annealing; Ising model; penalty methods; resource-constrained project scheduling; hybrid quantum-classical; minor embedding; Monte Carlo; digital twin.
Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.