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

1. Il Problema

Il Problema del Commesso Viaggiatore (TSP) è una sfida fondamentale nell'ottimizzazione combinatoria. I risolutori ad alte prestazioni come LKH (Lin-Kernighan-Helsgaun) non esplorano l'intero grafo completo delle possibili connessioni tra città, ma operano all'interno di un grafo candidato sparsificato (un sottoinsieme ridotto di archi).

La sfida principale risiede nel trade-off della sparsificazione del grafo:

• Se si mantengono troppi archi, il risolutore spreca tempo di calcolo.
• Se si rimuovono troppi archi, si rischia di eliminare gli archi che appartengono al tour ottimo, degradando la qualità della soluzione.

I metodi euristici esistenti, come $\alpha$-Nearest e POPMUSIC, offrono buone prestazioni ma non sono ottimali in tutte le situazioni:

• POPMUSIC: Produce grafi molto sparsi ma perde in "recall" (copertura degli archi ottimali) su istanze grandi o distribuzioni difficili.
• $\alpha$-Nearest: È più stabile nel recall ma produce grafi più densi.
• Metodi basati su ML esistenti: Spesso operano sul grafo completo (costoso) o sono limitati a distanze euclidee, fallendo su altri tipi di metriche (es. MAN_2D, GEO, ATT).

2. Metodologia: L'Approccio a Due Stadi

Gli autori propongono una pipeline innovativa a due stadi che applica l'apprendimento automatico (ML) non sul grafo completo, ma su un grafo candidato già parzialmente sparsificato.

Stadio 1: Massimizzazione del Recall (Unione Euristica)

Invece di scegliere una singola euristica, il metodo costruisce un grafo di base unendo gli archi selezionati da due euristiche complementari:
$$E_{union} = E_{\alpha\text{-Nearest}} \cup E_{\text{POPMUSIC}}$$

• Obiettivo: Garantire una copertura quasi perfetta (near-perfect recall) degli archi del tour ottimo.
• Segnale Chiave: Questa unione crea un segnale di "provenienza della fonte" (source-provenance). Un arco può provenire da $\alpha$-Nearest, da POPMUSIC, o da entrambi. Gli archi presenti in entrambe le liste hanno un'alta probabilità di essere ottimali, mentre quelli presenti in una sola sono candidati alla rimozione.

Stadio 2: Potatura Appresa (Learned Pruning)

Su questo grafo di base denso ma ad alto recall, viene addestrato un modello di ML per classificare e rimuovere gli archi meno importanti.

• Feature Engineering: Le caratteristiche estratte per ogni arco sono agnostico rispetto al tipo di distanza (non dipendono dalle coordinate cartesiane, ma solo dai pesi degli archi, ranghi, rapporti e statistiche locali). Questo permette al modello di funzionare su qualsiasi convenzione TSPLIB (EUC_2D, MAN_2D, ATT, GEO).
• Modelli: Vengono testati Logistic Regression (LR), Linear SVM e XGBoost.
• Regola di Selezione: Invece di una soglia globale, viene utilizzata una regola a livello di nodo. Per ogni nodo, gli archi incidenti sono ordinati per punteggio; si mantengono gli archi superiori finché la massa cumulativa (softmax) non supera una soglia $\eta$, garantendo un minimo di connettività per la fattibilità del tour.

3. Contributi Chiave

1. Pipeline a Due Stadi: È il primo approccio che applica la potatura appresa a un grafo candidato già sparsificato (unione di euristiche) invece che al grafo completo. Questo riduce drasticamente la complessità del problema di apprendimento.
2. Segnale di Provenienza: L'uso dell'unione di due euristiche fornisce un segnale predittivo robusto ("dual-source" vs "single-source") che rende l'apprendimento efficace anche con modelli semplici come la regressione logistica.
3. Generalizzazione: Il metodo funziona su 4 tipi di distanze TSPLIB e 5 distribuzioni spaziali, superando i limiti dei metodi neurali attuali che sono spesso vincolati alle sole distanze euclidee.
4. Scalabilità: Il metodo diventa più vantaggioso man mano che la dimensione del problema ($N$) aumenta, dove le euristiche singole tendono a degradare.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su istanze da $N=50$ a $N=500$.

• Riduzione della Densità: Il metodo riduce la densità del grafo candidato del 37-47% rispetto al grafo di unione di base, mantenendo una copertura degli archi ottimali $\ge$ 99.69% su tutte le dimensioni e distribuzioni.
• Prestazioni del Risolutore (LKH):
  • L'uso di grafi potati accelera il risolutore LKH di un fattore 1.20x - 1.28x senza aumentare il gap di ottimalità (anzi, in alcuni casi lo riduce leggermente).
  • La regressione logistica (LR) mostra le migliori prestazioni di velocità, mentre XGBoost offre il miglior compromesso tra densità e copertura.
• Confronto con Metodi Neurali: Su istanze euclidee (EUC_2D), il metodo proposto supera in copertura (fino al 99.95%) e densità i recenti metodi basati su Deep Learning (DIFUSCO, AttGCN, DIMES), che spesso faticano su distribuzioni difficili e richiedono GPU.
• Robustezza: Il modello addestrato su $N=100$ generalizza bene su istanze fino a $N=500$ (5 volte la dimensione di addestramento).
• Casi Difficili: Su distribuzioni "Corridor" (corridoio), dove gli archi ottimali sono lunghi e atipici localmente, la copertura scende leggermente (98.96% a $N=500$), ma rimane superiore all'uso di POPMUSIC da sola.

5. Significato e Conclusioni

Questo lavoro dimostra che l'integrazione di euristiche classiche con l'apprendimento automatico può superare i limiti di entrambi gli approcci presi singolarmente.

• Efficienza: Spostare il carico di lavoro dal grafo completo al grafo unione permette di usare modelli ML leggeri e veloci, eliminando la necessità di GPU potenti.
• Versatilità: La capacità di gestire diverse metriche di distanza rende il metodo applicabile a scenari reali complessi (es. logistica su sfera, distanze di rete) dove i metodi basati su coordinate geometriche falliscono.
• Scalabilità: L'approccio risolve il problema del degrado delle prestazioni delle euristiche su larga scala, offrendo una soluzione robusta per istanze TSP di grandi dimensioni.

In sintesi, il paper propone una soluzione pratica ed efficiente che bilancia perfettamente la necessità di ridurre lo spazio di ricerca (sparsificazione) mantenendo la garanzia di trovare soluzioni di alta qualità, superando i limiti attuali sia delle euristiche pure che dei metodi di apprendimento profondo end-to-end.