Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition
Anna Joliot, M. Yassine Naghmouchi, Wesley da Silva Coelho · 2025
This paper presents key enhancements to our previous work [1] 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 highdensity Benders cuts per iteration. Extensive numerical results demonstrate significant improvements compared to our previous approach: the feasibility rate increases from $\mathbf{6 8 \%}$ to $\mathbf{1 0 0 \%}$, and the optimality rate rises from $\mathbf{5 2 \%}$ to $\mathbf{8 6 \%}$. These advancements provide a solid foundation for future hybrid quantum-classical optimization solvers.