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

Technische Samenvatting: Hybride Quantum-Klassieke End-to-End Pipeline voor het Oplossen van MILP's

Probleemstelling
Mixed-Integer Lineaire Programmeringsproblemen (MILP) zijn centraal in besluitvormingsprocessen met een hoge impact in sectoren zoals logistiek en supply chain management, maar zijn computationeel uitdagend vanwege hun combinatorische aard. Hoewel decompositietechnieken zoals Benders Decompositie (BD) breed worden gebruikt om grootschalige MILP's op te lossen door ze te scheiden in een masterprobleem (MP) en subproblemen (SP), lijden ze vaak aan trage convergentie. Deze convergentie is kritisch afhankelijk van de selectie van informatieve "cuts" (constraints) die aan het masterprobleem worden toegevoegd. Vorig werk door Paterakis [1] stelde voor om quantum annealing te gebruiken voor de stap van cut-selectie—geformuleerd als een Minimum Set Cover probleem—om dit proces te versnellen. Echter, quantum annealing vereist kostbare minor-embedding procedures die aanzienlijke overhead introduceren wanneer men probeert op te schalen.

Methodologie
Dit artikel presenteert een end-to-end hybride quantum-klassiek optimalisatieframework dat de Multiple Cuts via Multiple Solutions (MCMS) Benders decompositie-aanpak uitbreidt. De kerninnovatie is het vervangen van de quantum annealing-stap door gate-gebaseerde Quantum Approximate Optimization Algorithm (QAOA) implementaties.

Het framework werkt als volgt:

1. MCMS Benders Decompositie: Het algoritme genereert meerdere kandidaatoplossingen per iteratie, waarbij meerdere subproblemen parallel wordt opgelost om een pool van kandidaat-cuts te produceren.
2. Cut Selectie als QUBO: Om te voorkomen dat het masterprobleem computationeel te zwaar wordt door een excessief aantal cuts, wordt een subset van informatieve cuts geselecteerd. Dit wordt geformuleerd als een Minimum Set Cover probleem, dat vervolgens wordt gemapt naar een Quadratic Unconstrained Binary Optimization (QUBO) instantie.
3. QAOA Integratie: In tegenstelling tot de voorgaande annealing-gebaseerde aanpak, lost dit framework de QUBO op met behulp van QAOA. De pipeline interface met drie verschillende solvers:
   • Fermioniq's Ava: Een tensor netwerk circuit emulator.
   • MPS-JuliQAOA: Een open-source Matrix Product State (MPS) emulator gebouwd in Julia.
   • IBM Quantum: Directe uitvoering op superconducting quantum hardware (IBM Eagle processor).
4. Casestudy: Het framework wordt geëvalueerd op het Vehicle Routing Problem (VRP), een canoniek logistiek optimalisatieprobleem. De studie maakt gebruik van een gestandaardiseerde benchmark uit QOptLib (20 klanten, 4 voertuigen) en willekeurige toy-instanties (5 klanten) om de haalbaarheid van de pipeline te testen.

Belangrijkste Bijdragen

• Gate-Based Uitbreiding: Het artikel breidt het bestaande HQC-MCMS framework uit van quantum annealing naar gate-gebaseerde quantum computing, wat uitvoering mogelijk maakt op zowel tensor netwerk emulators als superconducting quantum processors.
• End-to-End Implementatie: De auteurs demonstreren succesvol een volledig functionele pipeline die QAOA subroutines integreert in een klassieke Benders decompositie loop.
• Empirische Benchmarking: De studie biedt een vergelijkende analyse van de prestaties van de pipeline over verschillende solver backends (klassieke Cbc, MPS-JuliQAOA, Fermioniq, en IBM Quantum) op VRP-instanties.

Resultaten
De experimentele resultaten leveren verschillende cruciale inzichten op over de huidige levensvatbaarheid van quantumvoordeel in deze specifieke context:

• Klassieke Prestaties: In de volledig klassieke setting (met gebruik van Cbc voor cut-selectie) vindt de pipeline succesvol haalbare oplossingen voor de 20-klanten VRP-instantie, waarbij de optimaliteitsgap over iteraties afneemt. De Multi-Cut aanpak (door meer subproblemen te gebruiken) leidt tot haalbare oplossingen in minder iteraties.
• Runtime Bottlenecks: Analyse van de klassieke pipeline laat zien dat de cut-selectiestap slechts een klein deel van de totale iteratietijd in beslag neemt. Het grootste deel van de rekentijd wordt besteed aan het oplossen van het Master Probleem.
• Quantum Prestaties: Wanneer de cut-selectiestap wordt vervangen door QAOA (gebruikmakend van MPS-JuliQAOA) op een toy-probleem, neemt de totale runtime aanzienlijk toe vergeleken met de klassieke aanpak. De studie merkt op dat MPS-JuliQAOA veel minder efficiënt is dan de klassieke solver Cbc voor het minimum set cover probleem op deze schaal.
• QAOA Output: Experimenten op quantum hardware en emulators laten zien dat voor de geteste configuraties de meerderheid van de QAOA samples resulteert in onhaalbare oplossingen (dat wil zeggen, ze vormen geen geldige set cover). Hoewel diepere circuits ($p=3$) meer optimale kosten-samples opleverden dan vlakkere circuits ($p=1$), overtrof de algehele prestatie de klassieke methoden niet.

Betekenis en Claims
Het artikel concludeert met een bescheiden beoordeling van de huidige staat van het framework. De auteurs stellen expliciet dat voor de geteste probleemgroottes en configuraties, quantum advantage onwaarschijnlijk is. De primaire reden is tweeledig:

1. De cut-selectiestap, die het doel is voor quantum acceleratie, is geen computationele bottleneck in de huidige klassieke MCMS pipeline; het oplossen van het Master Probleem domineert de runtime.
2. De klassieke solver (Cbc) presteert aanzienlijk beter dan de QAOA-implementaties voor de specifieke Minimum Set Cover instanties die op deze schaal zijn gegenereerd.

De auteurs benadrukken dat hoewel de pipeline technisch functioneel is en een reproduceerbare stap demonstreert richting quantum-enhanced optimalisatie, de vertaling van het set cover probleem naar QUBO een substantiële overhead introduceert. Zij beargumenteren dat toekomstig onderzoek zich moet richten op grotere schaal benchmarking waar de cut-selectiestap mogelijk een meer significante bottleneck wordt, en waar krachtigere Quantum Processing Units (QPUs) potentieel waarde kunnen bieden. De studie dient als een waarschuwende empirische analyse, die benadrukt dat huidige quantummethoden nog geen versnelling bieden voor deze specifieke decompositiestap in praktische, klein- tot middelgrote instanties.