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

Technische Zusammenfassung: Hybride Quanten-klassische End-to-End-Pipeline zur Lösung von MILPs

Problemstellung
Gemischt-ganzzahlige lineare Optimierungsprobleme (Mixed-Integer Linear Programming, MILP) sind zentral für hochwirksame Entscheidungsprozesse in Branchen wie der Logistik und dem Lieferkettenmanagement, stellen jedoch aufgrund ihrer kombinatorischen Natur eine große Herausforderung dar. Während Dekompositionstechniken wie die Benders-Dekomposition (BD) weit verbreitet sind, um großskalige MILPs durch die Trennung in ein Masterproblem (MP) und Subprobleme (SP) zu lösen, leiden sie oft unter einer langsamen Konvergenz. Diese Konvergenz hängt entscheidend von der Auswahl informativer „Cuts“ (Nebenbedingungen) ab, die dem Masterproblem hinzugefügt werden. Vorherige Arbeiten von Paterakis [1] schlugen vor, Quantum Annealing für den Schritt der Cut-Selektion zu verwenden – formuliert als Minimum Set Cover Problem –, um diesen Prozess zu beschleunigen. Quantum Annealing erfordert jedoch kostspielige Minor-Embedding-Verfahren, die beim Skalieren einen erheblichen Overhead verursachen.

Methodik
Diese Arbeit präsentiert einen End-to-End-Hybrid-Quanten-Klassik-Optimierungsrahmen, der den Multiple Cuts via Multiple Solutions (MCMS) Benders-Dekompositionsansatz erweitert. Die zentrale Innovation besteht darin, den Quantum-Annealing-Schritt durch Gate-basierte Implementierungen des Quantum Approximate Optimization Algorithm (QAOA) zu ersetzen.

Der Rahmen funktioniert wie folgt:

1. MCMS Benders-Dekomposition: Der Algorithmus generiert pro Iteration mehrere Kandidatenlösungen, indem er mehrere Subprobleme parallel löst, um einen Pool an Kandidaten-Cuts zu erzeugen.
2. Cut-Selektion als QUBO: Um zu verhindern, dass das Masterproblem aufgrund einer übermäßigen Anzahl von Cuts rechenintensiv wird, wird eine Teilmenge informativer Cuts ausgewählt. Dies wird als Minimum Set Cover Problem formuliert, welches anschließend auf eine Quadratic Unconstrained Binary Optimization (QUBO)-Instanz abgebildet wird.
3. QAOA-Integration: Im Gegensatz zum bisherigen Annealing-basierten Ansatz löst dieser Rahmen das QUBO mittels QAOA. Die Pipeline interagiert mit drei verschiedenen Solvern:
   • Fermioniq's Ava: Ein Tensor-Netzwerk-Schaltkreis-Emulator.
   • MPS-JuliQAOA: Ein Open-Source Matrix Product State (MPS) Emulator, der in Julia entwickelt wurde.
   • IBM Quantum: Direkte Ausführung auf supraleitender Quantenhardware (IBM Eagle Prozessor).
4. Fallstudie: Der Rahmen wird für das Vehicle Routing Problem (VRP), ein kanonisches Logistikoptimierungsproblem, evaluiert. Die Studie nutzt einen standardisierten Benchmark aus QOptLib (20 Kunden, 4 Fahrzeuge) sowie zufällige Toy-Instanzen (5 Kunden), um die Durchführbarkeit der Pipeline zu testen.

Zentrale Beiträge

• Gate-basierte Erweiterung: Die Arbeit erweitert den bestehenden HQC-MCMS-Rahmen von Quantum Annealing zu Gate-basiertem Quantencomputing, was die Ausführung sowohl auf Tensor-Netzwerk-Emulatoren als auch auf supraleitenden Quantenprozessoren ermöglicht.
• End-to-End-Implementierung: Die Autoren demonstrieren erfolgreich eine voll funktionsfähige Pipeline, die QAOA-Subroutinen in eine klassische Benders-Dekompositions-Schleife integriert.
• Empirisches Benchmarking: Die Studie bietet eine vergleichende Analyse der Performance des Rahmens über verschiedene Solver-Backends (klassisch Cbc, MPS-JuliQAOA, Fermioniq und IBM Quantum) für VRP-Instanzen.

Ergebnisse
Die experimentellen Ergebnisse liefern mehrere kritische Erkenntnisse bezüglich der aktuellen Durchführbarkeit eines Quantenvorteils in diesem spezifischen Kontext:

• Klassische Performance: In der voll klassisch konfigurierten Umgebung (unter Verwendung von Cbc für die Cut-Selektion) findet die Pipeline erfolgreich zulässige Lösungen für die 20-Kunden-VRP-Instanz, wobei die Optimierungslücke über die Iterationen hinweg abnimmt. Der Multi-Cut-Ansatz (unter Verwendung von mehr Subproblemen) führt zu zulässigen Lösungen in weniger Iterationen.
• Runtime-Engpässe: Eine Analyse der klassischen Pipeline zeigt, dass der Schritt der Cut-Selektion nur einen kleinen Bruchteil der gesamten Iterationszeit beansprucht. Der Großteil der Rechenzeit wird durch das Lösen des Masterproblems aufgewendet.
• Quanten-Performance: Wenn der Cut-Selektionsschritt durch QAOA (unter Verwendung von MPS-JuliQAOA) bei einem Toy-Problem ersetzt wird, erhöht sich die Gesamtlaufzeit im Vergleich zum klassischen Ansatz signifikant. Die Studie stellt fest, dass MPS-JuliQAOA bei dieser Skala wesentlich ineffizienter ist als der klassische Solver Cbc für das Minimum Set Cover Problem.
• QAOA-Output: Experimente auf Quantenhardware und Emulatoren zeigen, dass für die getesteten Konfigurationen die Mehrheit der QAOA-Samples zu unzulässigen Lösungen führt (d. h. sie bilden kein gültiges Set Cover). Während tiefere Schaltkreise ($p=3$) mehr optimale Kostensamples lieferten als flachere ($p=1$), übertraf die Gesamtleistung die klassischen Methoden nicht.

Bedeutung und Behauptungen
Die Arbeit schließt mit einer bescheidenen Bewertung des aktuellen Zustands des Rahmens ab. Die Autoren stellen explizit fest, dass für die getesteten Problemgrößen und Konfigurationen ein Quantenvorteil unwahrscheinlich ist. Der Hauptgrund ist zweifach:

1. Der Schritt der Cut-Selektion, der Ziel für die Quantenbeschleunigung ist, stellt im aktuellen klassischen MCMS-Pipeline keinen Rechenengpass dar; das Lösen des Masterproblems dominiert die Laufzeit.
2. Der klassische Solver (Cbc) ist für die spezifischen Minimum Set Cover Instanzen in dieser Größenordnung den QAOA-Implementierungen weit überlegen.

Die Autoren betonen, dass die Überführung des Set-Cover-Problems in ein QUBO erhebliche Overheads einführt, obwohl die Pipeline technisch funktionsfähig ist und einen reproduzierbaren Schritt in Richtung quantengestützter Optimierung darstellt. Sie argumentieren, dass zukünftige Forschung auf größer angelegte Benchmarks fokussieren muss, in denen der Cut-Selektionsschritt ein signifikanterer Engpass sein könnte und in denen leistungsfähigere Quantum Processing Units (QPUs) potenziell einen Mehrwert bieten könnten. Die Studie dient als empirische Analyse, die aufzeigt, dass aktuelle Quantenmethoden noch keinen Geschwindigkeitsvorteil für diesen spezifischen Dekompositionsschritt in praktischen, klein- bis mittelgroßen Instanzen bieten.