Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

Probleemstelling

Hoogpresterende oplossers voor het Travelling Salesman Problem (TSP), zoals LKH (Lin-Kernighan-Helsgaun), werken niet met alle mogelijke randen in een volledig graaf, maar zoeken binnen een gesparsificeerde kandidaat-graaf (een klein subset van randen). De uitdaging bij het construeren van deze graaf is een delicate afweging:

• Te veel randen: De solver verspillen tijd aan het onderzoeken van irrelevante paden.
• Te weinig randen: De solver mist randen die essentieel zijn voor de optimale toer, wat leidt tot suboptimale oplossingen.

De twee leidende heuristieken, $\alpha$-Nearest en POPMUSIC, hebben elk hun sterke en zwakke punten:

• POPMUSIC is zeer spaarzaam (weinig randen) en behoudt de optimale toer goed op kleine schaal, maar de "recall" (het vermogen om de optimale randen te vinden) degradeert aanzienlijk bij grotere probleemgroottes en moeilijke ruimtelijke verdelingen.
• $\alpha$-Nearest is dichter (meer randen) maar behoudt een stabielere recall over verschillende schalen.
  Geen enkele bestaande methode is zowel extreem spaarzaam als betrouwbaar over alle probleemgroottes en verdelingen heen. Bestaande machine learning-benaderingen werken vaak op het volledige graaf (wat rekenkundig duur is) en zijn beperkt tot Euclidische afstanden.

Methodologie: Een Twee-Stadia Aanpak

De auteurs stellen een nieuwe twee-stadia methode voor om de dichtheid van een kandidaat-graaf te verminderen zonder de kwaliteit van de oplossing te verliezen.

Stadium 1: Maximale Recall (Heuristische Unie)
In plaats van te proberen de perfecte graaf direct te vinden, wordt eerst een basisgraaf geconstrueerd die bijna alle relevante randen bevat. Dit wordt gedaan door de unie te nemen van de randen gegenereerd door $\alpha$-Nearest en POPMUSIC:
$$E_{union} = E_{\alpha} \cup E_{pop}$$
Dit creëert een graaf met een zeer hoge dekking (near-perfect recall), maar deze is nog steeds te dicht. Cruciaal hierbij is het creëren van een "source-provenance" signaal: voor elke rand is bekend of deze uit één heuristiek komt of uit beide. Randen die in beide heuristieken voorkomen, zijn statistisch gezien zeer waarschijnlijk onderdeel van de optimale toer.

Stadium 2: Gelaarde Pruning (Machine Learning)
Op deze reeds gesparsificeerde basisgraaf wordt een machine learning-model getraind om de minst belangrijke randen te verwijderen (prunen).

• Functies: De modellen gebruiken functies die puur gebaseerd zijn op randgewichten en lokale statistieken (rangordes, verhoudingen, z-scores), niet op coördinaten. Dit maakt de methode agnostisch ten opzichte van afstandstypen (werkt voor EUC_2D, ATT, MAN_2D, GEO).
• Bron-provenance: Een cruciale invoer is of een rand uit één of beide heuristieken komt.
• Modellen: Er worden lichte modellen getraind (Logistieke Regressie, Lineaire SVM, XGBoost) om een score te geven aan elke rand.
• Selectieregel: In plaats van een globale drempelwaarde, wordt per knooppunt een lokale softmax-distributie gebruikt om de top-randen te behouden, waarbij een minimum aantal randen per knooppunt wordt gegarandeerd om de toer haalbaar te houden.

Belangrijkste Bijdragen

1. Twee-stadia pijplijn: De eerste methode die leert op een reeds gesparsificeerde heuristische graaf in plaats van op het volledige graaf. Dit verlaagt de rekenkosten drastisch en verbetert de generalisatie.
2. Universele toepasbaarheid: De methode werkt over vier verschillende TSPLIB-afstandstypen en vijf ruimtelijke verdelingen, zonder dat er specifieke aanpassingen nodig zijn voor het type afstand.
3. Effectiviteit van de unie: Het combineren van twee heuristieken creëert een sterk signaal (source-provenance) dat het leerprobleem voor het ML-model vereenvoudigt. Zelfs een simpele Logistieke Regressie presteert uitstekend dankzij dit signaal.
4. Schalingsvoordeel: De methode wordt juist waardevoller naarmate de probleemgrootte toeneemt, waar traditionele heuristieken zoals POPMUSIC falen.

Resultaten

De methode is getest op probleemgroottes van $N=50$ tot $N=500$ over 20 verschillende TSP-families.

• Dichtheid vs. Dekking: De twee-stadia methode (Union + XGBoost) vermindert de dichtheid van de kandidaat-graaf met 37% tot 47% (van ~6N randen naar ~3N randen) terwijl ≥99,69% van de randen van de optimale toer behouden blijft, zelfs bij $N=500$ (5x de trainingsgrootte).
• Oplosser Prestaties: Wanneer de gesparsificeerde graaf aan LKH wordt gegeven, resulteert dit in een snelheidsverbetering van 1,20x tot 1,28x vergeleken met de ongesparsificeerde unie-graaf, zonder dat de optimaliteitsgap (kwaliteit van de oplossing) verslechtert.
• Vergelijking met Neuronale Netwerken: Op Euclidische instances ($N=500$) overtreft de methode recente neurale sparsificatiemethoden (zoals DIFUSCO, AttGCN, DIMES) zowel in dekking als in dichtheid. Bovendien werkt de voorgestelde methode op CPU en is niet beperkt tot Euclidische afstanden, terwijl neurale methoden vaak GPU vereisen en alleen op Euclidische data trainen.
• Ablatie-studie:
  • Zonder Stadium 1 (direct trainen op het volledige graaf) faalt de methode door het gebrek aan structuur en class-imbalance.
  • POPMUSIC alleen werkt goed op kleine schaal, maar degradeert bij $N \ge 200$. De unie + ML overtreft POPMUSIC alleen vanaf $N=200$.
  • De "Corridor"-verdeling (met lange, globale randen) blijft een uitdaging, maar de unie-methode presteert hier nog steeds beter dan de individuele heuristieken.

Betekenis en Conclusie

Dit onderzoek toont aan dat het combineren van klassieke heuristieken met machine learning een krachtige strategie is voor TSP. Door de ML-fase te laten werken op een "veilige" basisgraaf (de unie) in plaats van het volledige graaf, wordt het leerprobleem veel eenvoudiger en robuuster.

De kerninzicht is dat het source-provenance signaal (of een rand door beide heuristieken wordt ondersteund) een zeer betrouwbare indicator is voor de kwaliteit van een rand. Dit stelt de auteurs in staat om een enkel, lichtgewicht model te trainen dat generaliseert over verschillende schalen en afstandstypen, en dat aanzienlijke snelheidswinst biedt voor state-of-the-art TSP-oplossers zonder in te leveren op de oplossingskwaliteit. De methode is vooral waardevol voor grootschalige TSP-problemen waar traditionele heuristieken tekortschieten.