Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Research Overview

This paper investigates the integration of the Quantum Approximate Optimization Algorithm (QAOA) into a Benders decomposition framework to solve Mixed-Integer Linear Programming (MILP) problems, specifically focusing on the Vehicle Routing Problem (VRP). Benders decomposition is a classical technique that partitions complex optimization problems into a master problem and several subproblems. A critical, often computationally expensive, step in this process is 'cut selection'—choosing which constraints to add to the master problem to improve convergence.

The researchers extend a previously proposed hybrid framework that uses quantum annealing for cut selection by implementing gate-based QAOA. They test this pipeline using three different backends: Fermioniq’s Ava tensor network emulator, the open-source MPS-JuliQAOA emulator, and IBM Quantum superconducting hardware. The team evaluates the framework on standardized VRP instances (20 customers, 4 vehicles) and smaller toy problems to assess whether delegating the cut selection step to a quantum processor provides a meaningful performance boost.

Findings and Implications

The empirical results show that for the tested instances, the cut selection step is not a significant bottleneck; the vast majority of computation time is spent on solving the master problem classically. Furthermore, when the team replaced the classical cut selection with QAOA on an emulator for a toy problem, the total runtime increased significantly compared to the classical baseline. This suggests that for problems of this size, the overhead of quantum-classical communication and the limitations of current QAOA implementations outweigh any potential benefits. The authors conclude that while the end-to-end pipeline is functional, achieving quantum advantage will require much larger-scale problems where the cut selection step becomes a true computational bottleneck.