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

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.