QAOA-Assisted Benders' Decomposition for Mixed-integer Linear Programming

Abstract

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 …

Citation

Z. Zhao, L. Fan, Y. Guo, Y. Wang, Z. Han, and L. Hanzo, "QAOA-Assisted Benders' Decomposition for Mixed-integer Linear Programming." IEEE International Conference on Communications (ICC), Denver, CO, 2024.