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.
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 68% to 100%, and the optimality rate rises from 52% to 86%. These advancements provide a solid foundation for future hybrid quantum-classical optimization solvers.
This paper presents a hybrid classical-quantum approach to solve mixed-integer linear programming (MILP) using neutral-atom quantum computations. We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem, where the MP is addressed using a neutral-atom device, after being transformed into a quadratic unconstrained binary optimization (QUBO) model, with an automatized procedure. Our MILP to QUBO conversion tightens the upper bounds of the continuous variables involved, positively impacting the required qubit count, and the convergence of the algorithm. To solve the QUBO, we develop a heuristic for atom register embedding and apply a variational algorithm for pulse shaping. In addition, we implement a proof of concept that outperforms existing solutions. We also conduct preliminary numerical results: In a series of small MILP instances our algorithm identifies over 95% of feasible solutions of high quality, outperforming classical BD approaches where the MP is solved using simulated annealing.
The Benders’ decomposition algorithm is a technique in mathematical programming for complex mixed-integer linear programming (MILP) problems with a particular block structure. The strategy of Benders’ decomposition can be described as a strategy of divide and conquer. The Benders’ decomposition algorithm has been employed in a variety of applications such as communication, networking, and machine learning. However, the master problem in Benders’ decomposition is still NP-hard, which motivates us to employ quantum computing. In the paper, we propose a hybrid quantum-classical Benders’ decomposition algorithm. We transfer the Benders’ decomposition’s master problem into the quadratic unconstrained binary optimization (QUBO) model and solve it by the state-of-the-art quantum annealer. Then, we analyze the computational results and discuss the feasibility of the proposed algorithm. Due to our reformulation in the master problem in Benders’ decomposition, our hybrid algorithm, which takes advantage of both classical and quantum computers, can guarantee the solution quality for solving MILP problems.
Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
Mixed-integer linear programs (MILPs) are fundamental to power system operations but are challenging to solve due to their NP-hard nature. Quantum annealing, which seeks to find the ground state of an Ising model–a minimization of a quadratic binary function–offers potential speedups for solving combinatorial optimization problems. However, converting MILPs into quadratic unconstrained binary optimization (QUBO) problems often requires lots of slack variables, leading to significant qubit overhead and limiting the capability of quantum annealers. In this work, we propose an efficient formulation approach that generates a QUBO representation of a targeted MILP without introducing auxiliary binary variables. Geometrically, our method approximates the value function of the MILP with a quadratic binary function leveraging a simple convex optimization subroutine. We prove the existence of the QUBO representation, which preserves the MILP’s optimal solution and objective value with the same number of binary variables. The proposed approach is validated on several instances of the security-constrained unit commitment (SCUC) problem, with test cases featuring up to 288 binary variables, demonstrating its efficacy in reducing qubit overhead for quantum-classical hybrid Benders decomposition frameworks.
Mixed-integer linear programs are widely used to model optimization problems involving both discrete and continuous variables, but remain computationally challenging due to the combinatorial complexity. To exploit the potential advantages of quantum computing in tackling the combinatorial optimization part, recent efforts have explored hybrid quantum-classical Benders decomposition frameworks, which delegate the discrete master problem to quantum solvers like annealers while solving the continuous subproblem classically. However, these approaches typically rely on penalty-based formulations that are heuristic in nature, offer no guarantee of recovering the exact master optimum, require delicate penalty tuning, and introduce slack-register overhead that inflates circuit size and distorts the problem's native structure. In this work, we propose a Grover Adaptive Search based Benders Decomposition (GAS-BD) algorithm that circumvents penalty terms by directly encoding Benders cuts into a novel quantum oracle. The designed oracle-based quantum solver searches for constraint-satisfying master solutions by leveraging Grover's potential quadratic speedup, while the subproblem loop is handled by a classical solver. Simulation results shows that GAS-BD matches the convergence of classical Benders and exhibits greater stability than penalty-based hybrid baselines, while remaining executable on current NISQ hardware. These results demonstrate a practical and penalty-free path for embedding exact Benders logic into Grover-style quantum search.
Bilevel programming problems (BLPPs) frequently appear in hierarchical decision-making contexts, including supply chain network design, critical infrastructure defense, and energy market equilibrium. These problems are NP-hard, posing significant computational challenges due to their nested structure. Classical exact solvers often struggle when the upper-level (leader) objective involves dense quadratic interactions, as linearization techniques typically induce an exponential increase in variables and constraints. Conversely, Quantum Annealing (QA) approaches offer potential advantages for quadratic optimization but suffer from resolution errors and qubit scarcity when handling continuous lower-level variables directly. To address these limitations, this study proposes a Hybrid Quantum Benders Decomposition (HQBD) framework. The method decomposes the Quadratic-Linear BLPP into a quantum master problem, which manages discrete combinatorial decisions with quadratic terms, and a classical subproblem, which handles continuous resource allocation. Numerical experiments on highly frustrated 3D Torus topologies demonstrate the framework’s algorithmic scalability up toN= 343 variables (2343combinatorial states), a scale where state-of-the-art classical exact solvers (Gurobi MIQP) trigger a 600-second timeout due to dense quadratic constraints. Furthermore, to mitigate early-stage barren plateaus commonly found in Benders-QUBO integrations, we introduce a “Relaxed Resource Strategy.” To fully address existing literature gaps and align with quantum computing standards, this revised study introduces a comprehensive sensitivity analysis of the relaxation parameters and expands the scalability benchmarking across five spatial dimensions. Statistical robustness analysis over 20 independent trials reveals that the optimized strategy achieves instantaneous convergence (Mean = 1.0 iteration), completely bypassing the exponential classical complexity wall.