Commesso Viaggiatore con Premi: Abbiamo Sfondato il Muro dell’1.6!

Ciao a tutti, appassionati di sfide complesse e soluzioni eleganti! Oggi voglio parlarvi di un’avventura nel mondo dell’ottimizzazione combinatoria, un campo che può sembrare astruso ma che, vi assicuro, ha implicazioni molto concrete. Avete presente il classico problema del commesso viaggiatore (TSP)? Quello in cui un povero venditore deve visitare un elenco di città minimizzando la distanza totale percorsa, tornando poi al punto di partenza. Un rompicapo affascinante e notoriamente difficile (NP-hard, per i più tecnici tra voi).

Bene, ora immaginate una variante ancora più realistica: il Prize-Collecting TSP (PCTSP). Qui, il nostro commesso viaggiatore non è obbligato a visitare tutte le città. Può decidere di saltarne qualcuna, ma attenzione: per ogni città non visitata, c’è una penalità da pagare! L’obiettivo diventa quindi trovare un tour che minimizzi la somma della lunghezza del percorso e delle penalità accumulate per le città escluse. Pensateci: quante volte, pianificando un viaggio, ci si chiede se una certa deviazione valga davvero la pena? Ecco, il PCTSP formalizza proprio questo dilemma!

Una Breccia nel Muro dell’Approssimazione

Essendo un problema NP-hard, trovare la soluzione ottima in tempi ragionevoli per istanze grandi è praticamente impossibile. Ci si affida quindi ad algoritmi di approssimazione, che cercano soluzioni “abbastanza buone” in tempi polinomiali, garantendo che il costo della soluzione trovata non sia peggiore di un certo fattore rispetto all’ottimo. Per anni, il miglior fattore di approssimazione per il PCTSP si attestava poco sotto 1.774. Un buon risultato, certo, ma noi ricercatori siamo testardi e cerchiamo sempre di limare, migliorare, spingere i limiti un po’ più in là.

Ebbene, amici, tenetevi forte: abbiamo sviluppato un nuovo algoritmo che fa proprio questo, e lo fa meglio di prima! Parliamo di un fattore di approssimazione che scende sotto quota 1.6, per la precisione a 1.599. Può sembrare un piccolo passo, ma nel mondo degli algoritmi di approssimazione, ogni decimale conquistato è una vittoria sudata. Questo risultato si basa su una garanzia relativa alla naturale rilassazione di programmazione lineare (LP) del problema, un potente strumento matematico che ci aiuta a “inquadrare” la soluzione.

Come Abbiamo Fatto? La Ricetta del Successo (Semplificata)

Senza addentrarci in dettagli troppo tecnici che potrebbero farvi sbadigliare, vi do un’idea del nostro approccio. Partiamo, come detto, da una soluzione della rilassazione LP. Una delle chicche è sfruttare una scomposizione nota di queste soluzioni LP in una serie di alberi radicati. Immaginate di poter “distribuire” la soluzione frazionaria su diversi alberi.

Il nostro algoritmo prende uno di questi alberi e, qui sta una delle novità, esegue un’attenta fase di “pruning” (potatura). Un po’ come un abile giardiniere che taglia i rami secchi o superflui per far crescere meglio la pianta, noi eliminiamo parti dell’albero per ottimizzare la struttura. Dopodiché, applichiamo una tecnica chiamata “correzione di parità” sui nodi rimanenti. Questo passaggio, ispirato al celebre algoritmo di Christofides-Serdyukov per il TSP classico, assicura che ogni “città” nel nostro sottografo abbia un numero pari di “strade” che entrano/escono, permettendoci di costruire un ciclo euleriano e, da lì, il nostro tour finale.

La cosa affascinante è che, con un’analisi più semplice del nostro metodo, eravamo già riusciti a dimostrare un fattore di approssimazione pari a (1+√5)/2 ≈ 1.618, ovvero la sezione aurea! Non è incredibile come certi numeri fondamentali della matematica spuntino fuori nei contesti più impensati? Ma non ci siamo accontentati: con qualche accorgimento tecnico in più e un’analisi più raffinata, siamo riusciti a scendere fino al già citato 1.599.

Non Solo Tour Completi: Miglioramenti anche per i Percorsi (Prize-Collecting Stroll)

Ma le buone notizie non finiscono qui! Il nostro approccio si è rivelato efficace anche per una variante del problema nota come Prize-Collecting Stroll (PCS). In questo caso, invece di un tour chiuso, cerchiamo un percorso (stroll) tra due città specifiche, sempre con la possibilità di saltare altre città pagando una penalità. Anche qui, abbiamo fatto un bel balzo in avanti: il nostro metodo porta a un fattore di approssimazione di 1.6662, migliorando significativamente il precedente miglior risultato di 1.926.

Per ottenere questo risultato sul PCS, abbiamo prima mostrato che un’estensione diretta del nostro algoritmo per PCTSP raggiunge un’approssimazione di 5/3 (circa 1.6667). Poi, abbiamo notato uno sbilanciamento nelle perdite tra costo degli archi e penalità. Combinando il nostro algoritmo con un approccio classico di “threshold rounding” (arrotondamento a soglia), opportunamente calibrato per bilanciare le perdite in direzione opposta, siamo riusciti a limare ulteriormente quel piccolo decimale, arrivando a 1.6662.

Un Po’ di Contesto Storico e Prospettive Future

È importante ricordare che questi risultati si inseriscono in una lunga tradizione di ricerca. I primi algoritmi a fattore costante per il PCTSP risalgono agli anni ’90. Da allora, c’è stata una serie di miglioramenti progressivi, passando per fattori come 2.5, 2, e poi via via scendendo. Il precedente “campione” era un algoritmo del 2013 di Blauth e Nägele, con il suo 1.774.

Il nostro lavoro si basa su alcune delle loro idee, come la scomposizione in alberi, ma introduce una fase di pruning e una correzione di parità che si sono rivelate più semplici da analizzare e, alla fine, più efficaci. La domanda che ora ci poniamo è: riusciremo un giorno ad avvicinarci al mitico fattore 3/2 dell’algoritmo di Christofides-Serdyukov per il TSP classico? O magari a trovare un metodo che, dato un algoritmo α-approssimato per TSP, ne produca uno α-approssimato (o quasi) per PCTSP? La strada è ancora lunga, ma ogni passo avanti è fonte di grande soddisfazione.

Per chi fosse interessato ai dettagli più tecnici, il nostro algoritmo per PCTSP, in breve, funziona così:

1. Risolviamo la rilassazione LP del PCTSP.
2. Applichiamo una tecnica chiamata “splitting off” per gestire i vertici con valori y_v (che indicano quanto un vertice è “visitato” dalla soluzione frazionaria) molto piccoli.
3. Utilizziamo la scomposizione in alberi (Lemma 1 nel paper originale) sulla soluzione LP modificata.
4. Per ogni albero T ottenuto e per diverse soglie egamma;, eseguiamo il “pruning”: troviamo il sottoalbero minimale T’ che copre tutti i vertici v in T con y_v ege; egamma;. Questo è il “core” dell’albero.
5. Aggiungiamo a T’ un matching di costo minimo sui suoi vertici di grado dispari (correzione di parità).
6. Trasformiamo il grafo risultante (che ha tutti i vertici di grado pari) in un tour e calcoliamo il suo costo (lunghezza + penalità).
7. Restituiamo il miglior tour trovato tra tutte le combinazioni di alberi e soglie.

L’analisi, soprattutto per raggiungere il 1.599, diventa piuttosto sofisticata e coinvolge la scelta randomizzata (poi derandomizzata) di alcuni parametri, ma l’idea di fondo è quella di bilanciare al meglio il costo del tour e le penalità pagate.

Insomma, è un campo di ricerca vivo e stimolante! Spero di avervi trasmesso un po’ dell’entusiasmo che proviamo quando riusciamo a spingere un po’ più in là i confini della conoscenza (e dell’efficienza algoritmica!).

Fonte: Springer