2996. QUBO Enhancement Through Preprocessing Techniques: Application to the Bin Packing Problem
Invited abstract in session WB-16: Beyond the limits of QUBO formalism, stream Quantum OR .
Wednesday, 10:30-12:00Room: Esther Simpson 2.07
Authors (first author is the speaker)
| 1. | Amina El Yaagoubi
|
| ICL, Junia, Université Catholique de Lille, LITL, F-59000 Lille, France | |
| 2. | Amélia Durbec
|
| ICL, Junia, Universit´e Catholique de Lille, LITL, F-59000 Lille, France | |
| 3. | Samuel Deleplanque
|
| Univ. Lille, CNRS, Centrale Lille, Junia, Univ. Polytechnique Hauts-de-France, UMR 8520 - IEMN - Lille, France |
Abstract
This study investigates the application of Quantum Annealing (QA) to solve the Bin Packing Problem (BPP) using a QUBO (Quadratic Unconstrained Binary Optimization) framework. While QA presents a promising approach for tackling complex combinatorial problems, practical implementation faces scalability challenges due to qubit limitations and embedding constraints on current quantum hardware. To address these issues, we introduce two preprocessing techniques: Slack Variable Reduction, which minimizes unnecessary variables, and Symmetry Elimination, which removes redundant configurations. Experiments conducted on D-Wave’s Advantage System demonstrate that these strategies effectively reduce qubit consumption, shorten chain lengths, and improve embedding feasibility. While these reductions significantly improve performance, the QUBO formulation's inherent quadratic growth in variables remains a limiting factor for larger instances, posing challenges for embedding on current quantum hardware. Nevertheless, our findings highlight that strategic preprocessing is crucial for extending the range of solvable BPP instances, offering promising insights for advancing quantum optimization in real-world scenarios.
Keywords
- Combinatorial Optimization
- Mathematical Programming
Status: accepted
Back to the list of papers