Hybrid Quantum Benders' Decomposition for Mixed-integer Linear Programming

Abstract

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 …

Citation

Z. Zhao, L. Fan, and Z. Han, "Hybrid Quantum Benders' Decomposition for Mixed-integer Linear Programming." IEEE Wireless Communications and Networking Conference (WCNC), 2022, pp. 2536-2540.