Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

Diese Studie stellt eine Vorverarbeitungsmethode vor, die durch die Einschränkung auf kostengünstigste Nachbarkanten die Komplexität des Traveling Salesman Problems reduziert und damit sowohl die Rechenzeit als auch die Optimalitätslücke bei klassischen und quantenbasierten Optimierungslösungen verbessert.

Das Wesentliche

Das Problem: Der überforderte Kurier

Stellen Sie sich vor, Sie sind ein Kurier, der 50 verschiedene Pakete in einer Stadt verteilen muss. Sie wollen den kürzesten Weg finden, der Sie an jeden Ort bringt und Sie wieder zu Ihrem Startpunkt zurückführt, ohne einen Ort doppelt anzufahren. Das klingt einfach, ist aber ein mathatisches Albtraum-Szenario.

Warum? Weil die Anzahl der möglichen Routen mit jedem zusätzlichen Ort explodiert. Bei 10 Orten gibt es schon Millionen Möglichkeiten, bei 50 Orten mehr als Atome im Universum. Ein Computer, der jede einzelne Möglichkeit durchprobieren will, würde länger brauchen als das Alter des Universums. Das ist das klassische „Problem des Handlungsreisenden" (TSP).

Die Lösung: Der kluge Filter (CAF)

Die Autoren dieses Papiers haben eine clevere Idee entwickelt, die sie CAF nennen (Cost-Based Arc Filtering). Man kann sich das wie einen erfahrenden Stadtführer vorstellen, der einem Touristen sagt: „Vergiss die langen, unnötigen Umwege! Bleib nur bei den nächsten Nachbarn."

Normalerweise könnte ein Kurier von jedem Haus zu jedem anderen Haus in der Stadt fahren. Das CAF-Verfahren schneidet jedoch alle diese „fernen" Verbindungen ab. Es behält für jeden Ort nur die kürzesten Verbindungen zu den nächsten Nachbarn bei.

Die Analogie des Gartens:
Stellen Sie sich einen riesigen, dichten Wald vor (alle möglichen Wege). Um einen Weg zu finden, muss man durch den ganzen Wald laufen. CAF ist wie ein Gärtner, der die hohen Bäume und dichten Sträucher an den Rändern wegschneidet und nur einen schmalen, gut begehbareren Pfad durch das Zentrum des Waldes übrig lässt. Der Pfad ist viel kürzer, aber er führt immer noch zum Ziel.

Warum funktioniert das? (Die Magie der Mathematik)

Man könnte denken: „Wenn wir Wege wegschneiden, finden wir vielleicht gar keine Lösung mehr!"
Die Autoren haben jedoch einen mathematischen Trick angewendet (basierend auf einem alten Theorem von Dirac). Sie schneiden nicht willkürlich, sondern so viel, dass jeder Ort immer noch mindestens so viele direkte Nachbarn hat, wie die Hälfte der Gesamtzahl der Städte.

Die Analogie des Partys:
Stellen Sie sich eine Party vor, bei der jeder Gast mit jedem anderen sprechen kann. Das ist chaotisch. CAF sagt: „Jeder Gast muss nur mit den 50 % der anderen Gäste sprechen, die ihm am nächsten stehen." Die Mathematik garantiert, dass man trotzdem einen perfekten Kreislauf finden kann, bei dem jeder genau einmal besucht wird. Die „Feasibility" (Machbarkeit) bleibt also erhalten.

Der Test: Klassisch vs. Quanten

Die Forscher haben diesen Filter auf zwei Arten getestet:

1. Der klassische Computer (wie ein Super-Gelehrter):
   Hier hat CAF Wunder gewirkt. Der Computer musste weniger Möglichkeiten durchrechnen. Das Ergebnis: Die Berechnung war oft doppelt so schnell, und die Lösung war genauso gut wie ohne Filter. Es ist, als würde man einem Sucher sagen: „Suche nur in diesem einen Zimmer, nicht im ganzen Haus."

2. Der Quanten-Computer (wie ein magischer Wahrsager):
   Quantencomputer sind extrem mächtig, aber sie haben eine riesige Schwäche: Sie können nur sehr kleine Probleme direkt lösen, weil ihre „Gedächtniskapazität" (Qubits) begrenzt ist.

   • Ohne Filter: Der Quantencomputer war bei nur 10–11 Städten schon völlig überfordert und gab auf.
   • Mit CAF: Durch das Wegschneiden der unnötigen Wege passte das Problem plötzlich in den kleinen Speicher des Quantencomputers! Sie konnten Probleme mit bis zu 15 Städten lösen, was vorher unmöglich war.

Das Fazit

Die Botschaft der Studie ist einfach: Man muss nicht alles wissen, um das Beste zu finden.

Indem man den Suchraum intelligent einschränkt (nur die besten Nachbarn zulässt), macht man das Problem für Computer viel handhabbarer.

• Für normale Computer spart es Zeit.
• Für Quantencomputer (die Zukunftstechnologie) ist es der Schlüssel, um überhaupt erst größere, reale Probleme zu lösen.

Es ist wie beim Packen eines Koffers für eine Reise: Man nimmt nicht alles mit, was man besitzt, sondern nur das Nötigste und Beste. Und trotzdem kommt man am Ziel an – und zwar schneller.

Technische Zusammenfassung

Titel: Traveling Salesman Problem mit einer Vorverarbeitungsmethode für klassische und Quantenoptimierung

Autoren: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

---

1. Problemstellung

Das Traveling Salesman Problem (TSP) ist ein fundamentales kombinatorisches Optimierungsproblem, bei dem eine Route gefunden werden muss, die jede Stadt genau einmal besucht und zum Startpunkt zurückkehrt, wobei die Gesamtkosten minimiert werden.

• Herausforderungen: Das Problem ist NP-schwer. Die Suche nach einer optimalen Lösung wird durch das exponentielle Wachstum des Suchraums und die Notwendigkeit einer großen Anzahl von Nebenbedingungen zur Eliminierung von Teilrouten (Subtour-Eliminierung) erschwert.
• Quanten-Hürden: Der Einsatz von Quantencomputern (insbesondere Quantum Annealing und hybride Quanten-Klassische Solver) für das TSP ist derzeit stark eingeschränkt. Hardware-Beschränkungen (Qubit-Anzahl, Konnektivität) und die komplexe Struktur der QUBO-Modelle (Quadratic Unconstrained Binary Optimization) erlauben bisher nur die Lösung sehr kleiner oder künstlicher Instanzen.

2. Methodik: Cost-Based Arc Filtering (CAF)

Die Autoren stellen eine neue Vorverarbeitungsmethode namens Cost-Based Arc Filtering (CAF) vor, um die Größe des Optimierungsmodells drastisch zu reduzieren, ohne die Lösbarkeit des Problems zu gefährden.

• Prinzip: Anstatt alle möglichen Kanten (Boolesche Variablen) im Modell zu berücksichtigen, wird für jeden Knoten nur eine Teilmenge der Nachbarknoten behalten.
• Auswahlkriterium: Für jeden Knoten $i$ werden die Kanten $(i, j)$ nach ihren Kosten $c_{ij}$ sortiert. Es werden nur die $k$ Nachbarn mit den geringsten Kosten behalten.
• Theoretische Fundierung: Die Anzahl der zu behaltenden Nachbarn wird als $k = \lceil n/2 \rceil$ (aufgerundete Hälfte der Knotenanzahl) definiert.
  • Begründung: Dies basiert auf dem Satz von Dirac aus der Graphentheorie. Dieser besagt, dass ein Graph mit $n$ Knoten ($n \ge 3$) Hamiltonisch ist (d.h. einen Zyklus enthält, der jeden Knoten genau einmal besucht), wenn der minimale Grad jedes Knotens mindestens $n/2$ beträgt.
  • Garantie: Durch die Auswahl der $k = \lceil n/2 \rceil$ günstigsten Kanten pro Knoten bleibt der resultierende reduzierte Graph garantiert Hamiltonisch. Die Existenz einer gültigen TSP-Lösung wird also theoretisch bewahrt.
• Optimalitätsannahme: Die Methode nutzt die strukturellen Eigenschaften euklidischer TSP-Instanzen aus, bei denen optimale Touren tendenziell aus kurzen Verbindungen zwischen nahen Knoten bestehen. Lange Verbindungen werden durch das Filtern entfernt.

3. Lösungsansatz

Die Studie verfolgt einen mehrstufigen Ansatz:

1. Formulierung: Das TSP wird als ganzzahliges lineares Programm (ILP) formuliert.
2. Vorverarbeitung: Die CAF-Methode wird angewendet, um die Menge der Kandidatenkanten zu reduzieren.
3. Klassische Optimierung: Die Modelle (mit und ohne CAF) werden mit dem kommerziellen Solver Gurobi gelöst.
4. Quantenoptimierung: Die vorverarbeiteten Modelle werden im Constrained Quadratic Model (CQM) Framework formuliert und mit dem hybriden Solver D-Wave LeapCQMHybrid (auf dem Advantage2-System) gelöst.

4. Wichtige Beiträge und Ergebnisse

A. Reduktion der Modellgröße

• Die CAF-Methode reduziert die Anzahl der Entscheidungsvariablen (Kanten) um durchschnittlich ca. 30 % im Vergleich zur vollständigen Formulierung.
• Der Reduktionsgrad nimmt mit der Größe des Problems ($n$) zu, was die Skalierbarkeit für größere Instanzen verbessert.

B. Klassische Optimierung (Gurobi)

• Lösungsqualität: Für Instanzen bis $n=20$ wurde in beiden Fällen (mit und ohne CAF) die Optimalität bewiesen. Die CAF-Vorverarbeitung ändert den optimalen Zielfunktionswert nicht.
• Rechenzeit: Die Vorverarbeitung führt zu einer signifikanten Beschleunigung. Bei Instanzen mit $n \ge 10$ sank die Rechenzeit um durchschnittlich 32 %. Bei $n=20$ wurde die Zeit mehr als halbiert.
• Grenzfälle: Bei $n=21$ erreichte der Solver ohne CAF die Zeitgrenze (300 s) ohne Beweis der Optimalität. Mit CAF wurde zwar auch die Zeitgrenze erreicht, aber eine deutlich bessere (niedrigere) Zielfunktion erzielt.

C. Quantenoptimierung (D-Wave Hybrid Solver)

• Skalierbarkeit: Dank der Reduktion der Variablen konnten TSP-Instanzen mit bis zu 15 Kunden erfolgreich mit dem Quanten-Hybrid-Solver bearbeitet werden. Dies ist eine signifikante Steigerung gegenüber der Literatur, die sich meist auf sehr kleine Instanzen beschränkt.
• Qualitätsverbesserung:
  • Bei kleineren Instanzen ($n \le 11$) wurde in allen Läufen die optimale Lösung gefunden.
  • Bei größeren Instanzen ($n=12$ bis $15$) führte CAF zu einer deutlichen Verringerung der Optimalitätslücke (Gap). Beispielsweise sank der Gap bei $n=13$ von 43 % (ohne CAF) auf 11 % (mit CAF).
  • Der durchschnittliche Gap über alle getesteten Instanzen sank um ca. 29–31 %.
• Effizienz: Die durchschnittliche Lösungszeit sank um ca. 5–17 %, da der Solver einen kompakteren Suchraum durchsuchen muss.

5. Signifikanz und Fazit

Die Arbeit demonstriert, dass eine intelligente Vorverarbeitung (Preprocessing) entscheidend ist, um die Lücke zwischen theoretischen Optimierungsmodellen und den aktuellen Fähigkeiten von Quantenhardware zu schließen.

• Theoretischer Wert: Der Nachweis, dass durch die Einhaltung des Dirac-Kriteriums ($k = \lceil n/2 \rceil$) die Feasibility (Durchführbarkeit) des Problems garantiert bleibt, ist ein wichtiger theoretischer Beitrag.
• Praktischer Wert: Die Methode macht TSP-Formulierungen für klassische Solver effizienter und ist ein Enabler für Quantenoptimierung. Sie ermöglicht es, realistischere Benchmark-Instanzen (aus TSPLIB) statt nur künstlicher Toy-Probleme auf Quantenhardware zu testen.
• Zukunftsperspektive: Die Autoren sehen Potenzial für iterative Verfahren, die das Modell dynamisch während des Lösungsprozesses verfeinern, um die Skalierbarkeit für noch größere Probleme weiter zu erhöhen.

Zusammenfassend zeigt die Studie, dass CAF die Komplexität des TSP effektiv reduziert, ohne die Lösungsqualität zu beeinträchtigen, und somit sowohl für klassische als auch für hybride Quanten-Klassische Optimierungsansätze eine wesentliche Verbesserung darstellt.