Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Technische Zusammenfassung: Ising-Maschinen-gestützte Large Neighborhood Search mit flexibel abstimmbarer Subproblem-Größe

Problemstellung
Ising-Maschinen dienen als heuristische Solver für kombinatorische Optimierung, indem sie nach Zuständen mit niedriger Energie in Ising- oder Quadratic Unconstrained Binary Optimization (QUBO)-Modellen suchen. Die direkte Anwendung auf groß angelegte, beschränkte Probleme (die „naive Methode“) stößt jedoch auf zwei primäre Schwierigkeiten:

1. Skalierbarkeit: Die Anzahl der binären Variablen in der QUBO-Formulierung übersteigt oft die Hardwarekapazität aktueller Ising-Maschinen.
2. Machbarkeit (Feasibility): Nebenbedingungen werden typischerweise als Strafterme integriert. Infolgedessen enthält der Suchraum unzulässige Lösungen, und Zustände mit niedriger Energie entsprechen nicht zwangsläufig hochqualitativen zulässigen Lösungen des ursprünglichen Problems.

Bestehende Ansätze wie Variable Fixing oder Divide-and-Conquer versuchen zwar, die Problemgröße zu reduzieren, kämpfen aber oft damit, die Subproblem-Größe mit der Fähigkeit zur Rekonstruktion zulässiger Lösungen des Originalproblems in Einklang zu bringen. Die Large Neighborhood Search (LNS) bietet ein Framework, bei dem eine zulässige aktuelle Lösung iterativ verbessert wird, indem ein Subproblem (eine „Nachbarschaft“) neu optimiert wird. Während LNS die Zulässigkeit bewahrt, sofern die Methode zur Generierung des Subproblems korrekt gestaltet ist, reagiert die Leistungsfähigkeit der Ising-Maschinen-gestützten LNS sehr empfindlich auf die Größe des Subproblems. Wenn das Subproblem zu klein ist, ist die potenzielle Verbesserung pro Iteration begrenzt; wenn es zu groß ist, verschlechtert sich die Lösungsqualität der Ising-Maschine aufgrund des expandierten Suchraums.

Methodik
Die Arbeit konzentriert sich auf zwei Probleme: das Vehicle Routing Problem (VRP) und das Quadratic Multiple Knapsack Problem (QMKP).

• Bestehende Methode (LNS-V): Für das VRP analysieren die Autoren eine vorangegangene Methode (LNS-V), welche eine Teilmenge von Fahrzeugen auswählt und deren gesamte Routen neu optimiert. Dies bewahrt zwar die Zulässigkeit, aber die Subproblem-Größe wird ausschließlich durch die Anzahl der ausgewählten Fahrzeuge ($V'$) gesteuert. Da die gesamte Route eines ausgewählten Fahrzeugs neu optimiert wird, skaliert die Anzahl der Variablen als $(V')^2(T-2)^2$ (wobei $T$ die Gesamtschritte darstellt). Dies führt zu einer groben Granularität; eine Änderung von $V'$ um eins kann einen massiven Sprung in der Variablenanzahl verursachen, was es schwierig macht, die Subproblem-Größe auf den optimalen Bereich für die Ising-Maschine abzustimmen.

• Vorgeschlagene Methode (LNS-VT): Um das Problem der Granularität anzugehen, schlagen die Autoren LNS-VT vor. Zusätzlich zur Auswahl von $V'$ Fahrzeugen führt LNS-VT einen neuen Parameter ein: die Anzahl der aufeinanderfolgenden Schritte ($T'$), die für jedes ausgewählte Fahrzeug neu optimiert werden sollen.

  • Mechanismus: Für jedes ausgewählte Fahrzeug wird ein zusammenhängendes Segment der Route (der Länge $T_{seg} = \min(T', \text{tatsächliche gültige Schritte})$) extrahiert. Das Subproblem optimiert die Zuweisung und Reihenfolge der Standorte innerhalb dieser spezifischen Segmente neu, während der Rest der Route unverändert bleibt.
  • Zulässigkeit: Durch das Fixieren der Standorte außerhalb der Extraktionsintervalle und die Sicherstellung, dass die extrahierten Segmente nur Nicht-Depot-Standorte beinhalten, garantiert die Methode, dass die Wiedereinfügung jeder zulässigen Subproblem-Lösung eine zulässige Lösung für das ursprüngliche VRP ergibt.
  • Variablenkontrolle: Die Anzahl der freien Variablen in LNS-VT beträgt näherungsweise $(V'T')^2$. Dies ermöglicht eine feingranulare Kontrolle über die Subproblem-Größe, unabhängig von den Gesamtschritten $T$ des Problems.

• Erweiterung auf QMKP: Die Autoren wenden dasselbe Konstruktionsprinzip auf das QMKP an. Sie konstruieren eine Methode zur Generierung von Subproblemen, die eine Teilmenge von Beuteln ($K'$) und eine Teilmenge von Artikeln ($N'$) auswählt, um diese neu zu optimieren. Diese Methode bewahrt die Zulässigkeit, indem Artikel, die nicht in der ausgewählten Menge enthalten sind, fixiert und die Kapazitätsbeschränkungen für die Restkapazität der ausgewählten Beutel angepasst werden.

Wichtigste Ergebnisse
Numerische Experimente wurden unter Verwendung eines 300-Standorte, 5-Fahrzeug-VRP und eines 200-Artikel, 5-Beutel-QMKP unter Nutzung der Fixstars Amplify AE Ising-Maschine durchgeführt.

• VRP-Leistung:

  • LNS-VT übertraf sowohl die naive Methode als auch die bestehende LNS-V.
  • Die beste LNS-VT-Einstellung (speziell $V'=2, T'=40$) reduzierte den Zielwert im Vergleich zu LNS-V nach 100 Iterationen um etwa 10 %.
  • LNS-VT erreichte die endgültige Lösungsqualität von LNS-V mit nur etwa 30 % der Iterationen.
  • Variablen-Sensitivität: Der optimale Subproblem-Größenbereich (bezogen auf die Nicht-Depot-Standort-Zuweidungsvariablen) lag zwischen 6.000 und 10.000. Die bestehende LNS-V konnte diesen Bereich mit $V' \ge 2$ nicht erreichen (ihr Minimum lag bei ~14.400 Variablen), was ihre unterlegene Leistung erklärt.
  • Dynamische Anforderungen: Die angemessene Subproblem-Größe änderte sich während des Suchprozesses. Größere Subprobleme waren in frühen Iterationen (hohe Zielwerte) effektiver, während kleinere Subprobleme in späteren Iterationen (Verfeinerung hochwertiger Lösungen) effektiver waren.

• QMKP-Leistung:

  • Die auf das QMKP angewandte LNS übertraf ebenfalls die naive Methode.
  • Die optimale Subproblem-Größe für QMKP wurde signifikant kleiner ermittelt, nämlich etwa 100 bis 150 Variablen.
  • Dieser drastische Unterschied zum VRP (6.000–10.000) zeigt, dass die optimale Subproblem-Größe von der spezifischen Problemklasse und der QUBO-Formulierung abhängt und nicht nur von den Fähigkeiten der Ising-Maschine.

Bedeutung und Behauptungen
Das Paper behauptet, dass für eine Ising-Maschinen-gestützte LNS bei groß angelegten, beschränkten Problemen die bloße Wahrung der Zulässigkeit (Feasibility Preservation) nicht ausreicht. Die Fähigkeit, die Subproblem-Größe flexibel abzustimmen, um den Leistungs-Sweet-Spot der Ising-Maschine zu treffen, ist ein kritischer Entwurfsfaktor.

Die Studie zeigt:

1. Die Einführung eines zusätzlichen Kontrollparameters (aufeinanderfolgende Schritte für VRP oder Artikel-/Beutelanzahl für QMKP) ermöglicht eine feingranulare Anpassung der Subproblem-Größe, was mit Methoden, die nur die Anzahl der ausgewählten Entitäten variieren, unmöglich ist.
2. Es existiert ein optimaler Bereich an Variablen für das Subproblem, der die Lösungsqualität maximiert, und dieser Bereich variiert signifikant zwischen verschiedenen Problemklassen (VRP vs. QMKP).
3. Die optimale Subproblem-Größe kann auch von der Qualität der aktuellen Lösung abhängen, was darauf hindeutet, dass statische Parametereinstellungen während des gesamten Suchprozesses nicht optimal sein können.

Die Autoren kommen zu dem Schluss, dass, obwohl ihre Ergebnisse spezifisch für die getesteten Instanzen und Maschineneinstellungen sind, das Prinzip der struktur-bewussten, flexibel abstimmbaren Subproblem-Generierung eine vielversprechende Richtung für die beschränkte kombinatorische Optimierung darstellt. Sie merken an, dass zukünftige Arbeiten darauf abzielen sollten, adaptive Strategien zu entwickeln, um Subproblem-Parameter basierend auf der Suchphase und der Problemstruktur automatisch zu wählen.