Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition

Abstract

This paper presents key enhancements to our previous work~\cite{naghmouchi2024mixed} on a hybrid Benders decomposition (HBD) framework for solving mixed integer linear programs (MILPs). In our approach, the master problem is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model and solved on a neutral-atom quantum processor using automated conversion techniques. Our enhancements address three critical challenges. First, to adapt to hardware constraints, we refine the QUBO formulation by tightening the bounds of continuous variables and employing an exponential encoding method that eliminates slack variables, thereby reducing the required qubit count. Second, to improve solution quality, we propose a robust feasibility cut generation method inspired by the L-shaped approach and implement a constructive penalty tuning mechanism that replaces manual settings. Third, to accelerate convergence, we introduce a multi-cut strategy that integrates multiple high-density Benders cuts per iteration. Extensive numerical results demonstrate significant improvements compared to our previous approach: the feasibility rate increases from 68 percent to 100 percent, and the optimality rate rises from 52 percent to 86 percent . These advancements provide a solid foundation for future hybrid quantum-classical optimization solvers.

References in corpus (8)

• Quantum computing with neutral atoms
• A Tutorial on Formulating and Using QUBO Models
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Penalty Weights in QUBO Formulations: Permutation Problems
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Quantum pricing-based column-generation framework for hard combinatorial problems
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
• Typical Approximation Performance for Maximum Coverage Problem