Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Dit artikel introduceert een tensor-netwerkformulering voor het Traveling Salesman Problem en diens varianten die gebruikmaakt van met de Boltzmann-verdeling gewogen lagen en tellingfilters om optimale rondreizen te identificeren via een sequentiële marginaalregel, dienend als heuristiek voor kleinschalige industriële toepassingen in plaats van als een superieur alternatief voor gespecialiseerde klassieke oplossingsmethoden.

De kern

Het Grote Plaatje: De "Reizende Verkoper"-puzzel Oplossen met een Nieuw Soort Rekenmachine

Stel je voor dat je een reizende verkoper bent. Je hebt een kaart met 10, 20 of zelfs 100 steden. Je moet elke stad precies één keer bezoeken en terugkeren naar huis, maar je wilt dit doen over de kortst mogelijke afstand om brandstof en tijd te besparen. Dit is het beroemde Reizende Verkoper Probleem (TSP).

Het probleem is dat naarmate je meer steden toevoegt, het aantal mogelijke routes explodeert. Het is alsof je probeert de perfecte sleutel te vinden in een hoop sleutels die zo snel groeit dat het controleren van elke enkele sleutel langer zou duren dan de leeftijd van het universum. Daarom worstelen computers hiermee.

Dit artikel introduceert een nieuwe manier om dit probleem aan te pakken met behulp van Tensornetwerken. Denk aan een tensornetwerk niet als een computerprogramma, maar als een groot, meerlagig filtersysteem.

De Analogie: De "Goudstof"-zeef

Stel je voor dat je een enorme zak zand hebt, gemengd met goudstof.

• Het Zand: Vertegenwoordigt alle slechte, lange, inefficiënte routes.
• Het Goud: Vertegenwoordigt de perfecte, kortste route.
• Het Doel: Je wilt het goud van het zand scheiden zonder naar elk korreltje afzonderlijk te kijken.

De auteurs bouwden een machine (het tensornetwerk) om dit te doen:

1. Het Initiële Mengsel (De Superpositie): Eerst creëert de machine een "superpositie". Stel je voor dat het magisch een kopie maakt van elke mogelijke route tegelijkertijd. Het is alsof je een miljoen verschillende versies van jezelf hebt, die elk een ander pad nemen.
2. De Weging (De Warmte): Vervolgens past de machine een "temperatuur" toe (genaamd $\tau$). Denk hierbij aan een warmtelamp.
   • De lange, inefficiënte routes (het zand) worden heet en veranderen in licht, waardoor ze vervagen.
   • De korte, efficiënte routes (het goud) blijven koel en zwaar.
   • De machine gebruikt wiskunde (Boltzmann-factoren) om de slechte routes sneller te laten verdwijnen dan de goede.
3. De Filters (De Regels): Dit is het belangrijkste deel. Je kunt niet zomaar elke route hebben; je kunt niet dezelfde stad twee keer bezoeken. De auteurs bouwden speciale Aftelfilters.
   • Stel je een bewaker voor bij elke stad. Als een reiziger probeert een stad te bezoeken waar hij al eerder was, slaat de bewaker de deur dicht voor die specifieke route.
   • Deze filters zijn "spaars", wat betekent dat ze zeer efficiënt zijn in het blokkeren van de verkeerde paden zonder elke enkele mogelijkheid handmatig te hoeven controleren.
4. Het Resultaat (De Marginale): Nadat alles door de warmte en de filters is gegaan, knijpt de machine alles samen. Het vraagt: "Als ik naar de eerste stad kijk, welke is dan het meest waarschijnlijk deel van de winnende route?" Het kiest die ene, vergrendelt deze en herhaalt het proces voor de tweede stad, en zo verder, totdat de hele route is opgebouwd.

Wat Ze Eigenlijk Deden (De Experimenten)

De auteurs beweerden niet dat deze methode een wondermiddel is dat elk probleem direct oplost. Ze waren zeer eerlijk over de beperkingen.

• Kleine Tests: Ze testten hun methode op kleine kaarten (5 tot 12 steden).
• Kalibratie: Ze ontdekten dat de "temperatuur"-instelling ($\tau$) cruciaal is. Als deze te laag is, verdwijnen de slechte routes niet genoeg. Als deze te hoog is, raakt de computer in de war door kleine wiskundige fouten. Ze moesten deze instelling zorgvuldig afstellen voor elke kaartgrootte.
• De Resultaten:
  • Toen ze de instellingen perfect afstelden, vond hun methode de perfecte route ongeveer 95% van de tijd op deze kleine kaarten.
  • Toen ze het vergeleken met standaard computermethoden (zoals "Gierig" of "Gesimuleerde Temperen"), was hun methode vaak beter in het vinden van de perfecte route.
  • Echter, gaven ze toe dat voor zeer grote kaarten de wiskunde nog steeds te zwaar wordt (exponentiële complexiteit), net als bij de oude methoden. Het is geen "polynoomtijd"-wonder; het is gewoon een andere, zeer gestructureerde manier om de wiskunde te doen.

Wereldse Test: Het Probleem van Taakherverdeling

Om te zien of dit buiten de theorie werkt, pasten ze het toe op een echt industrieel probleem voor ONCE (een Spaanse organisatie voor blinden).

• Het Probleem: Ze hadden werknemers toegewezen aan banen en sommige banen waren leeg. Ze moesten zien of het verplaatsen van een werknemer naar een nieuwe baan het hele team productiever zou maken.
• De Twist: Dit is niet precies een "reiskwestie", maar het is vergelijkbaar: je moet unieke banen toewijzen aan unieke mensen zonder dubbel te boeken.
• De Uitkomst: Ze vergeleken hun tensornetwerkmethode met twee andere krachtige hulpmiddelen (een kwantum-annealer en een digitale annealer).
  • De resultaten waren identiek wat betreft de totale productiviteitswinst.
  • De enige verschillen zaten in "gelijkspel"-situaties waarbij twee opties wiskundig gelijk waren; de machines kozen er gewoon willekeurig een andere uit.
  • Conclusie: Dit bewees dat hun methode werkt in de echte wereld en kan worden geïntegreerd in industriële software, zelfs als het deze specifieke taak niet verslaat door de gespecialiseerde hulpmiddelen.

De Conclusie

Het artikel presenteert een nieuw wiskundig gereedschapskist voor het oplossen van route- en toewijzingspuzzels.

• Het Goede: Het biedt een zeer duidelijke, modulaire manier om complexe regels te hanteren (zoals "bezoek niet dezelfde stad twee keer") en kan perfecte oplossingen vinden bij kleine problemen. Het is alsof je een zeer georganiseerde, regels volgend assistent hebt die nooit moe wordt van het controleren van beperkingen.
• Het Slechte: Het maakt enorme problemen niet magisch makkelijk. De wiskunde wordt nog steeds exponentieel moeilijker naarmate het probleem groeit. Het vereist zorgvuldige afstelling (kalibratie) om goed te werken.
• De Kernboodschap: Het is een krachtige nieuwe manier om over deze problemen na te denken en een stevig hulpmiddel voor specifieke, kleinere industriële taken, maar het is nog geen vervanging voor alle bestaande supersnelle oplossers.

Kortom: Ze bouwden een geavanceerde zeef die slechte routes kan filteren en de beste kan vinden, maar je moet het nog steeds de juiste instellingen geven om het goud te krijgen.

Technische samenvatting

Technische Samenvatting: Tensor-netwerkformulering van het Travelling Salesman-probleem en varianten

Probleemdefinitie
Het artikel behandelt het Travelling Salesman-probleem (TSP) en enkele van zijn generalisaties, waaronder het Tijdsafhankelijke TSP (TDTSP), het Job Reassignment Problem (JRP), en varianten met beperkingen op niet-herhaling, precedentieregels, groepsbeperkingen en bottleneck-doelstellingen. Het TSP wordt gedefinieerd als het vinden van de kortste route die $N$ knopen precies één keer bezoekt en terugkeert naar het startpunt, een bekend NP-moeilijk probleem. Hoewel exacte algoritmen zoals Held-Karp ($O(N^2 2^N)$) en branch-and-bound bestaan, kampen ze met exponentiële complexiteit die hun schaalbaarheid voor industriële gevallen beperkt. Daarentegen bieden heuristieken (bijvoorbeeld genetische algoritmen, lokale zoektocht) benaderende oplossingen zonder optimaliteitsgaranties. De auteurs merken op dat opkomende quantumalgoritmen (QAOA, VQE) momenteel worden beperkt door hardware-ruis (NISQ-tijdperk), wat de exploratie van klassieke technieken motiveert die eigenschappen van quantum-systemen nabootsen.

Methodologie
De kernbijdrage is een tensor-netwerk (TN) formulering die kandidaat-routes voorstelt als toestanden in een tensorproductruimte. De methode werkt via drie primaire mechanismen:

1. Tensor-netwerkconstructie:

   • Initialisatie ('+'): Creëert een uniforme superpositie van alle mogelijke knooptoewijzingen voor elke tijdstap.
   • Optimalisatie ('S'): Past een operator voor imaginaire tijdsontwikkeling toe $U = e^{-\tau C(\vec{y})}$, waarbij $\tau$ een dempingsfactor is en $C(\vec{y})$ de routekosten. Dit onderdrukt exponentieel configuraties met hoge kosten, analoog aan het vinden van de grondtoestand in quantum-systemen.
   • Beperkingfiltering ('F'): Introduceert Matrix Product Operator (MPO)-lagen om beperkingen af te dwingen. Voor het standaard TSP fungeren deze lagen als telfilters die garanderen dat elke knoop precies één keer voorkomt. De filters gebruiken binaire bond-indices om bij te houden of een specifieke knoop al is bezocht, wat effectief de beperking van het Levi-Civita-symbool $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$ implementeert.
   • Extractie ('+'): Een trace-laag somt de amplitude op om marginale gewichten te produceren.

2. Sequentiële marginale extractie:
   De oplossing wordt iteratief geëxtraheerd. Voor een vast prefix van de route berekent het algoritme het marginale gewicht $Z_p(a; \tau)$ voor elke kandidaat-knoop $a$ op de volgende positie. In de limiet van $\tau \to \infty$ en exacte rekenkunde is de knoop die dit gewicht maximaliseert gegarandeerd onderdeel van een optimale route (Propositie 3.2). Het algoritme selecteert de maximaliserende knoop, werkt het prefix bij en herhaalt dit totdat de route compleet is.

3. Generalisaties:
   Het raamwerk wordt aangepast voor diverse TSP-varianten door de filter- en evolutielagen te modificeren:

   • DNSNN (Verschillend Aantal Stappen/Knopen): Filters staan toe dat knopen tussen $N^0$ en $N^f$ keer voorkomen.
   • NMTSP (Niet-Markoviaans): Gebruikt hogere-orde MPO's om kosten te behandelen die afhankelijk zijn van $K$ voorgaande stappen.
   • BTSP (Bottleneck): Vervangt de kosten-evolutie door een laag die de maximale randkosten die zijn tegengekomen bijhoudt.
   • PTSP (Groepsbeperkt): Filters dwingen af dat precies één knoop per klasse wordt bezocht.
   • TSPP (Precedentie): Lokale projectoren onderdrukken knopen als hun vereiste voorgangers nog niet zijn verschenen.
   • JRP (Job Reassignment): Gemodelleerd als een lineaire toewijzingsprobleem waarbij een "geen-beweging"-toestand herhaalbaar is en specifieke vacatures uniek zijn.

4. Benadering en Complexiteit:
   De exacte contractie van het volledige tensor-netwerk is exponentieel, met schaling als $O(\hat{N}^4 2^{\hat{N}})$ voor dichte contractie per laag. Om grotere instanties aan te pakken, stellen de auteurs het volgende voor:

   • Lagenablatie: Toepassen van slechts een subset van beperkingslagen om complexiteit te verminderen, waarbij het resultaat wordt behandeld als een heuristiek.
   • Sparce-lokale contractie: Benutten van het deterministische, sparce karakter van de lokale filtertensors om polynoomiale prefactoren te verminderen (bijvoorbeeld van $O(\hat{N}^4 2^{\hat{N}})$ naar $O(\hat{N}^3 2^{\hat{N}})$) zonder de exponentiële schaling te veranderen.
   • Finiet-$\tau$-heuristiek: Gebruik van eindige precisie en eindig $\tau$ om de limiet bij nul temperatuur te benaderen, met erkenning dat numeriek contrast en degeneraties de oplossingskwaliteit beïnvloeden.

Kernbijdragen

• Expliciete marginale formule: Afleiding van een tensor-netwerk marginale vergelijking waarvan de limiet bij nul temperatuur en exacte rekenkunde een optimale haalbare route identificeert via een sequentiële marginale regel.
• Codering van beperkingen: Definitie van MPO-lagen voor telbeperkingen (niet-herhaling) toepasbaar op diverse combinatorische problemen.
• Generalisatieraamwerk: Een modulaire constructie die de TN-formaliteit aanpast aan TSP-varianten (TDTSP, JRP, BTSP, enz.) door specifieke tensorlagen te wijzigen.
• Implementatie van heuristiek: Een implementatie met eindige precisie en eindig $\tau$ die fungeert als een gekalibreerde heuristiek, met een analyse van haar gedrag met betrekking tot numeriek contrast en degeneratie.

Resultaten
De experimentele studie richt zich op kleine, synthetische instanties ($N \in \{5, \dots, 12\}$) om de correctheid en numeriek gedrag van de methode te valideren, in plaats van om computationele superioriteit ten opzichte van gespecialiseerde oplossers te claimen.

• Kalibratie: De parameter voor imaginaire tijd $\tau$ is afhankelijk van de grootte. Een kalibratiesweep ($\tau \in \{1, \dots, 40\}$) verbeterde het percentage optimale oplossingen aanzienlijk van 55,56% (bij $\tau=1$) naar 95,56% op de evaluatieset.
• Vergelijking met oplossers: Op kleine instanties bereikte de gekalibreerde TN-oplosser een optimaliteitspercentage van 95,24%, wat beter was dan NetworkX-greedy (26,67%) en gesimuleerde afkoeling (59,05%), maar onderdeed voor de exacte Held-Karp-referentie (100%).
• Lagenablatie: Het verwijderen van beperkingslagen degradeerde de oplossingskwaliteit, wat bevestigt dat de volledige filterset noodzakelijk is voor hoge nauwkeurigheid.
• Industrieel geval (JRP): In een proof-of-concept voor het ONCE Job Reassignment Problem produceerde de TN-methode oplossingen met geaccumuleerde kosten die identiek waren aan die van de Azure Digital Annealer, met uitzondering van degeneratieve gevallen waar meerdere optimale toewijzingen bestaan.

Betekenis en Claims
De auteurs stellen expliciet bescheidenheid ten opzichte van de computationele kracht van de methode. Zij claimen geen algemeen computationeel voordeel ten opzichte van gespecialiseerde klassieke oplossers (zoals Held-Karp, branch-and-cut, of algoritmen specifiek voor toewijzing) voor het algemene TSP.

• Formele representatie: Het werk wordt gepresenteerd als een "formele exacte-rekenkunde exponentiële-tijd representatie" en een "platform voor gecontroleerde benaderingen en uitbreidingen".
• Heuristisch karakter: De implementatie met finiet $\tau$ wordt gekarakteriseerd als een "gekalibreerde heuristiek met eindige precisie" waarvan het gedrag afhankelijk is van numeriek contrast en degeneraties.
• Nuttigheid: De primaire waarde ligt in het modulaire tensor-netwerkraamwerk, dat de systematische integratie van diverse beperkingen (precedentie, groepen, niet-Markoviaanse kosten) en de toepassing van benaderingstechnieken (verwijdering van lagen, sparce contracties) binnen een unified formalisme mogelijk maakt.
• Beperkingen: De methode behoudt exponentiële schaling in het slechtste geval. Problemen met numerieke stabiliteit (underflow, verlies van contrast in degeneratieve gevallen) en de behoefte aan grootte-afhankelijke kalibratie worden geïdentificeerd als significante beperkingen.

Kortom, het artikel biedt een rigoureuze tensor-netwerkformaliteit voor TSP en zijn varianten, waarbij het vermogen wordt aangetoond om optimale oplossingen op kleine instanties te herstellen en industriële beperkingen te integreren, terwijl wordt erkend dat het de fundamentele exponentiële complexiteit van het probleem niet overwint.