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

Technical Summary: Hybrid Quantum-Classical End-to-End Pipeline for Solving MILPs

Problem Statement
Mixed-Integer Linear Programming (MILP) problems are central to high-impact decision-making in industries such as logistics and supply chain management but are computationally challenging due to their combinatorial nature. While decomposition techniques like Benders Decomposition (BD) are widely used to solve large-scale MILPs by separating them into a master problem (MP) and subproblems (SP), they often suffer from slow convergence. This convergence is critically dependent on the selection of informative "cuts" (constraints) to add to the master problem. Previous work by Paterakis [1] proposed using quantum annealing to solve the cut selection step—formulated as a Minimum Set Cover problem—to accelerate this process. However, quantum annealing requires costly minor-embedding procedures that introduce significant overhead when scaling.

Methodology
This paper presents an end-to-end hybrid quantum-classical optimization framework that extends the Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition approach. The core innovation is replacing the quantum annealing step with gate-based Quantum Approximate Optimization Algorithm (QAOA) implementations.

The framework operates as follows:

1. MCMS Benders Decomposition: The algorithm generates multiple candidate solutions per iteration, solving multiple subproblems in parallel to produce a pool of candidate cuts.
2. Cut Selection as QUBO: To prevent the master problem from becoming computationally expensive due to an excessive number of cuts, a subset of informative cuts is selected. This is formulated as a Minimum Set Cover problem, which is then mapped to a Quadratic Unconstrained Binary Optimization (QUBO) instance.
3. QAOA Integration: Unlike the previous annealing-based approach, this framework solves the QUBO using QAOA. The pipeline interfaces with three distinct solvers:
   • Fermioniq's Ava: A tensor network circuit emulator.
   • MPS-JuliQAOA: An open-source Matrix Product State (MPS) emulator built in Julia.
   • IBM Quantum: Direct execution on superconducting quantum hardware (IBM Eagle processor).
4. Case Study: The framework is evaluated on the Vehicle Routing Problem (VRP), a canonical logistics optimization problem. The study utilizes a standardized benchmark from QOptLib (20 customers, 4 vehicles) and random toy instances (5 customers) to test the pipeline's feasibility.

Key Contributions

• Gate-Based Extension: The paper extends the existing HQC-MCMS framework from quantum annealing to gate-based quantum computing, enabling execution on both tensor network emulators and superconducting quantum processors.
• End-to-End Implementation: The authors successfully demonstrate a fully functional pipeline that integrates QAOA subroutines into a classical Benders decomposition loop.
• Empirical Benchmarking: The study provides a comparative analysis of the pipeline's performance across different solver backends (classical Cbc, MPS-JuliQAOA, Fermioniq, and IBM Quantum) on VRP instances.

Results
The experimental results yield several critical insights regarding the current viability of quantum advantage in this specific context:

• Classical Performance: In the fully classical setting (using Cbc for cut selection), the pipeline successfully finds feasible solutions for the 20-customer VRP instance, with the optimality gap decreasing over iterations. The Multi-Cut approach (using more subproblems) leads to feasible solutions in fewer iterations.
• Runtime Bottlenecks: Analysis of the classical pipeline reveals that the cut selection step consumes only a small fraction of the total iteration time. The majority of the computational time is spent solving the Master Problem.
• Quantum Performance: When the cut selection step is replaced by QAOA (using MPS-JuliQAOA) on a toy problem, the total runtime increases significantly compared to the classical approach. The study notes that MPS-JuliQAOA is much less efficient than the classical solver Cbc for the minimum set cover problem at this scale.
• QAOA Output: Experiments on quantum hardware and emulators show that for the tested configurations, the majority of QAOA samples result in infeasible solutions (i.e., they do not form a valid set cover). While deeper circuits ($p=3$) yielded more optimal cost samples than shallower ones ($p=1$), the overall performance did not surpass classical methods.

Significance and Claims
The paper concludes with a modest assessment of the framework's current state. The authors explicitly state that for the problem sizes and configurations tested, quantum advantage is unlikely. The primary reason is twofold:

1. The cut selection step, which is the target for quantum acceleration, is not a computational bottleneck in the current classical MCMS pipeline; the Master Problem solving dominates the runtime.
2. The classical solver (Cbc) vastly outperforms the QAOA implementations for the specific Minimum Set Cover instances generated at this scale.

The authors emphasize that while the pipeline is technically functional and demonstrates a reproducible step toward quantum-enhanced optimization, the translation of the set cover problem to QUBO introduces substantial overhead. They argue that future research must focus on larger-scale benchmarking where the cut selection step might become a more significant bottleneck, and where more powerful Quantum Processing Units (QPUs) could potentially offer value. The study serves as a cautionary empirical analysis, highlighting that current quantum methods do not yet provide a speedup for this specific decomposition step in practical, small-to-medium scale instances.