Metraipolis › archive › dc_d14c135dd511

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20853
License (as archived)
CC0-1.0
Archived
2026-10-10T02:05:01.226Z
SHA-256 of the archived text
84383bead46fd95d5c31f571953d8e713874ff0bbbf8096a4cdc9a6c1c34370e
Stable URL of this page
https://metraipolis.com/documento/dc_d14c135dd511

How to cite

Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware — arXiv:2609.20853 — arXiv (en), https://arxiv.org/abs/2609.20853 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d14c135dd511 (Metraipolis archive dc_d14c135dd511, sha256 84383bead46fd95d5c31f571953d8e713874ff0bbbf8096a4cdc9a6c1c34370e)
BibTeX
@misc{dcd14c135dd511,
  title = {Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware — arXiv:2609.20853},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20853},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d14c135dd511; sha256 84383bead46fd95d5c31f571953d8e713874ff0bbbf8096a4cdc9a6c1c34370e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20853. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.OC).
Categorie arXiv: Quantum Physics (quant-ph) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.20853 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T01:45:31.258Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).