Benders' decomposition (BD) algorithm constitutes a powerful mathematical programming method of solving mixed-integer linear programming (MILP) problems with a specific block structure. Nevertheless, BD still needs to solve an NP-hard quasi-integer programming master problem (MAP), which motivates us to harness the popular variational quantum algorithm (VQA) to assist BD. More specifically, we choose the popular quantum approximate optimization algorithm (QAOA) of the VQA family. We transfer the BD's MAP into a digital quantum circuit associated with a physically tangible problem-specific ansatz; and then solve it with the aid of a state-of-the-art digital quantum computer. Next, we evaluate the computational results and discuss the feasibility of the proposed algorithm. The hybrid approach advocated, which utilizes both classical and digital quantum computers, is capable of tackling many practical MILP problems in communication and networking, as demonstrated by a pair of case studies.
Benders' decomposition (BD) algorithm constitutes a powerful mathematical programming method of solving mixed-integer linear programming (MILP) problems with a specific block structure. Nevertheless, BD still needs to solve an NP-hard quasi-integer programming master problem (MAP), which motivates us to harness the popular variational quantum algorithm (VQA) to assist BD. More specifically, we choose the popular quantum approximate optimization algorithm (QAOA) of the VQA family. We transfer the BD's MAP into a digital quantum circuit associated with a physically tangible problem-specific ansatz; and then solve it with the aid of a state-of-the-art digital quantum computer. Next, we evaluate the computational results and discuss the feasibility of the proposed algorithm. The hybrid approach advocated, which utilizes both classical and digital quantum computers, is capable of tackling many practical MILP problems in communication and networking, as demonstrated by a pair of case studies.
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.
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.
Edge computing holds significant potential to revolutionize computation by providing rapid and widely accessible services to numerous devices at the network edge. For service providers, efficient service placement and workload allocation are critical to minimizing operational costs while ensuring high-quality user experiences. In this work, we formulate this problem as a mixed-integer linear program (MILP), which is computationally challenging due to its NP-hard nature. To address this, we propose an innovative hybrid quantum-classical algorithm that integrates recent advances in quantum computing with the Benders decomposition method. Specifically, the MILP is decomposed into a master problem, which, after a series of transformations, can be solved using a quantum annealer, and a linear programming subproblem handled by a classical solver. These two problems are iteratively updated and solved, with information exchanged between the quantum and classical solvers, until convergence is achieved. Numerical experiments validate the effectiveness and computational advantages of the proposed method, demonstrating its practical applicability to real-world edge computing scenarios.
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.
Quantum computing is emerging as a new computing resource that could be superior to conventional computing for certain classes of optimization problems. However, in principle, most existing approaches to quantum optimization are intended to solve unconstrained binary programming problems, while mixed-integer linear programming is of most interest in practice. We attempt to bridge the gap between the capability of quantum computing and real-world applications by developing a new approach for mixed-integer programming. The approach applies Benders decomposition to decompose the mixed-integer programming into binary programming and linear programming sub-problems, which are solved by a noisy intermediate-scale quantum processor and conventional processor, respectively. The algorithm is provably able to reach the optimal solution of the original mixed-integer programming problem. The algorithm is tested on a D-Wave 2000Q quantum processing unit and is shown to be effective for small-scaled test cases. We also test the algorithm on a mixed-integer programming inspired by power system applications. Many insights are drawn from the numerical results for both the capabilities and limitations of the proposed algorithm.
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.