Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

Questo articolo presenta un approccio iterativo basato sulla generazione dinamica di vincoli e su una fase di pre-elaborazione per ridurre la complessità del Problema del Commesso Viaggiatore, dimostrando sperimentalmente che tale metodologia migliora le prestazioni computazionali sia negli algoritmi classici che in quelli quantistici (inclusi annealing su D-Wave e solutori ibridi).

L'essenziale

🚚 Il Problema del Corriere Perfetto (e come i Computer Quantistici ci aiutano)

Immagina di essere un corriere che deve consegnare pacchi in 30 città diverse. Il tuo obiettivo è semplice: visitare ogni città una sola volta e tornare a casa, facendo il percorso più breve possibile per risparmiare benzina e tempo.

Questo è il Problema del Commesso Viaggiatore (in inglese Traveling Salesman Problem o TSP). Sembra facile, vero? In realtà, è uno dei problemi più ostici della matematica.

🤯 Il Problema: Troppi Percorsi, Troppi "Giri"

Il problema è che il numero di possibili percorsi cresce in modo esplosivo. Se hai 5 città, hai poche opzioni. Se ne hai 30, hai più percorsi possibili di quanti atomi ci siano nell'universo!

C'è però un trucco matematico: devi evitare di creare "sottocicli".

• Esempio: Immagina che il tuo percorso ti porti a visitare Milano, Torino e Genova, per poi tornare a Milano prima di aver visitato Roma o Napoli. Hai fatto un giro tondo (un sottociclo) e ti sei bloccato, lasciando altre città indietro.
• Per evitare questo, i matematici devono scrivere una regola per ogni possibile gruppo di città che potrebbe fare un giro da solo. Con 30 città, queste regole sono milioni. Scrivere tutte queste regole su un foglio di carta renderebbe il computer così lento da non finire mai il calcolo.

✂️ La Soluzione: Il "Taglio" Intelligente (Cutting-Plane)

Gli autori di questo studio hanno detto: "Perché scrivere tutte le regole fin dall'inizio? Scriviamole solo quando servono!".

Hanno usato una strategia chiamata Metodo del Taglio (Cutting-Plane).
Immagina di dover trovare un percorso perfetto in una foresta piena di sentieri sbagliati:

1. Il computer prova un percorso veloce, ignorando le regole complesse.
2. Se il computer si accorge che hai fatto un "giro tondo" (un sottociclo), allora taglia quel sentiero sbagliato aggiungendo una regola specifica solo per quel caso.
3. Riprova. Se fai un altro giro tondo, tagli anche quello.
4. Ripeti finché non trovi il percorso perfetto.

Invece di avere una mappa con un milione di divieti, ne hai solo pochi, quelli che servono davvero in quel momento. È come se invece di chiudere tutte le porte di una casa, chiudessi solo quelle da cui qualcuno sta cercando di entrare.

🧹 La Pulizia Preliminare (Filtraggio)

Prima di iniziare a tagliare, hanno anche fatto una pulizia preliminare.
Hanno guardato la mappa e detto: "Ehi, questa strada tra Roma e Milano è lunghissima e costosa. Nessuno la userebbe mai per fare il percorso più breve. Buttiamola via!".
Hanno eliminato i percorsi "stupidi" prima ancora di iniziare a calcolare. Questo ha reso il problema molto più piccolo e gestibile.

🤖 La Magia Quantistica: Il Computer che "Sente" la Soluzione

Qui entra in gioco la parte più affascinante: i Computer Quantistici (in particolare quelli di D-Wave).

• I Computer Classici (come il tuo PC): Sono come un esploratore che prova un sentiero alla volta. Se sbaglia, torna indietro e ne prova un altro. Con 30 città, ci metterebbe secoli.
• I Computer Quantistici: Sono come un esploratore che può sentire la pendenza di tutte le montagne contemporaneamente. Usano fenomeni strani della fisica (come il "tunneling") per saltare attraverso gli ostacoli e trovare la valle più bassa (la soluzione migliore) molto più velocemente.

Tuttavia, i computer quantistici attuali sono piccoli e fragili. Non riescono a gestire milioni di regole tutte insieme.

🚀 Il Risultato: Un Team Vincente

Gli autori hanno unito tre cose:

1. La pulizia preliminare (togliere le strade inutili).
2. Il metodo del taglio (aggiungere le regole solo quando serve).
3. Il computer quantistico (per trovare la soluzione veloce).

Cosa è successo?

• Con i computer classici, il metodo ha permesso di risolvere problemi che prima erano impossibili da calcolare in tempi ragionevoli.
• Con i computer quantistici diretti (senza aiuto), hanno risolto problemi fino a 12 città (un record per questo tipo di approccio diretto).
• Con i computer ibridi (un mix di classico e quantistico che lavorano insieme), hanno risolto problemi fino a 30 città con una precisione quasi perfetta (99% di successo).

💡 In Sintesi

Questo studio ci dice che non serve aspettare che i computer quantistici diventino giganteschi e perfetti per usarli. Se li aiutiamo con tecniche intelligenti (come tagliare le regole inutili e pulire la mappa prima), possiamo già oggi usarli per risolvere problemi complessi del mondo reale, come la logistica dei trasporti o la pianificazione delle consegne.

È come dire: "Non serve un motore di Formula 1 per vincere una gara di kart, basta guidare con intelligenza e avere la macchina giusta per il tracciato!".

Sommario tecnico

Titolo: Metodologia a piani di taglio tramite ottimizzazione quantistica per la risoluzione del Problema del Commesso Viaggiatore (TSP)

Autori: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero.
Affiliazione: Università della Calabria e ICAR-CNR (Italia).

---

1. Il Problema

Il Problema del Commesso Viaggiatore (TSP) è un classico problema di ottimizzazione combinatoria NP-hard, che mira a trovare il percorso più breve che visita un insieme di città esattamente una volta e ritorna al punto di partenza.
La sfida principale nella formulazione matematica del TSP (tipicamente tramite Programmazione Lineare Intera - ILP) risiede nella necessità di introdurre vincoli di eliminazione dei sottocicli (subtour elimination constraints).

• Il collo di bottiglia: Il numero di questi vincoli cresce esponenzialmente con il numero di città ($O(2^n)$). Includerli esplicitamente in un modello completo rende la formulazione intrattabile anche per istanze di dimensioni moderate.
• Contesto Quantistico: L'applicazione dell'ottimizzazione quantistica (in particolare l'Annealing Quantistico - QA) al TSP è limitata dalla capacità dei processori quantistici attuali (QPU) di gestire modelli con un numero elevato di variabili e vincoli complessi, specialmente quando i vincoli devono essere codificati tramite termini di penalità (modello QUBO).

2. Metodologia Proposta

Gli autori propongono un framework ibrido che combina tecniche consolidate di ricerca operativa con approcci di ottimizzazione quantistica. La strategia si basa su due pilastri fondamentali per ridurre la complessità del modello:

A. Approccio a Piani di Taglio (Cutting-Plane Approach - CPA)

Invece di includere tutti i vincoli di eliminazione dei sottocicli a priori, viene adottata una generazione dinamica dei vincoli (lazy constraint generation):

1. Si risolve inizialmente un modello rilassato contenente solo i vincoli di grado (ogni città ha un arco in entrata e uno in uscita).
2. Si analizza la soluzione ottenuta per rilevare la presenza di sottocicli (tour parziali).
3. Se vengono identificati sottocicli, i corrispondenti vincoli di eliminazione vengono aggiunti dinamicamente al modello ("tagli").
4. Il processo si ripete iterativamente fino a ottenere un tour Hamiltoniano valido (un singolo ciclo che visita tutte le città).
   Questo approccio mantiene la dimensione del modello gestibile, aggiungendo solo i vincoli strettamente necessari durante l'ottimizzazione.

B. Preprocessing basato sul Filtraggio degli Archi (Cost-based Arc Filtering - CAF)

Per ridurre ulteriormente lo spazio di ricerca, viene applicata una fase di preprocessing che elimina gli archi "non promettenti":

• Si analizza la struttura del grafo e le distanze tra le città.
• Per ogni nodo, vengono mantenuti solo gli archi uscenti verso i vicini più prossimi (basati sul costo), scartando quelli dominati o incompatibili con una soluzione ottima.
• Questo riduce il numero di variabili decisionali senza compromettere l'esistenza di un ciclo Hamiltoniano.

C. Sperimentazione su Paradigmi Diversi

Il framework proposto viene testato su tre approcci:

1. Ottimizzazione Classica: Risoluzione tramite solver commerciale (Gurobi).
2. Ottimizzazione Quantistica Diretta (QPU): Formulazione QUBO eseguita direttamente su un processore quantistico D-Wave (Advantage2). I vincoli sono codificati come termini di penalità.
3. Ottimizzazione Ibrida Quantistico-Classica: Utilizzo del modello CQM (Constrained Quadratic Model) risolto tramite solver ibridi D-Wave (LeapCQMHybrid), che combinano euristica classica e annealing quantistico.

3. Contributi Chiave

• Prima applicazione iterativa in QA: Questo lavoro rappresenta la prima applicazione di una generazione iterativa "lazy" dei vincoli di sottociclo all'interno di un framework di Annealing Quantistico per il TSP.
• Riduzione della complessità: Dimostra che la combinazione di CPA e CAF riduce drasticamente la dimensione del modello, rendendo fattibile la risoluzione di istanze standard (fino a 30-45 nodi) che sarebbero altrimenti intrattabili per i metodi quantistici diretti.
• Confronto sistematico: Fornisce un'analisi comparativa dettagliata tra formulazioni QUBO (dirette) e CQM (ibride), evidenziando i limiti attuali dell'hardware quantistico puro rispetto alle soluzioni ibride.
• Scalabilità: Riuscire a risolvere istanze di benchmark TSPLIB (come berlin52) con un approccio quantistico/ibrido, superando il limite delle piccole istanze (n < 10) tipico della letteratura precedente.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su istanze TSPLIB con un numero di vertici $V$ variabile da 5 a 45.

• Impatto sulla Complessità del Modello:

  • Il CAF riduce il numero di variabili decisionali del 20-35% (fino al 32% per istanze grandi).
  • Il CPA riduce il numero di vincoli del 95-100% rispetto alla formulazione completa (CILP), eliminando l'esplosione combinatoria.

• Ottimizzazione Classica:

  • La formulazione completa (CILP) diventa intrattabile per $V \ge 20$ (tempi di calcolo proibitivi).
  • La combinazione CPA + CAF risolve istanze fino a $V=45$ in frazioni di secondo, con tempi di calcolo trascurabili.

• Ottimizzazione Quantistica Diretta (QPU):

  • La formulazione completa (CILP) fallisce per $V \ge 6$ (nessuna soluzione fattibile).
  • L'approccio CPA migliora significativamente la fattibilità: soluzioni ottimali ottenute fino a $V=8$ (gap 1%), con un tasso di fattibilità del 40% fino a $V=10$. Per $V \ge 11$, l'approccio diretto non riesce a trovare soluzioni fattibili a causa dei limiti hardware e della complessità del modello QUBO.

• Ottimizzazione Ibrida (CQM):

  • Questo approccio ha mostrato le prestazioni migliori.
  • Ha raggiunto soluzioni ottimali (gap 0%) per tutte le istanze fino a $n=25$.
  • Per l'istanza più grande testata ($n=30$), ha ottenuto un gap di ottimalità dell'1% (soluzione quasi ottima) con un tempo di calcolo gestibile (~140 secondi totali).
  • La variabilità dei risultati è stata minima, dimostrando robustezza.

5. Significato e Conclusioni

Il lavoro dimostra che l'ottimizzazione quantistica pura (QPU diretto) è attualmente limitata dalla capacità di codificare vincoli globali complessi come quelli di eliminazione dei sottocicli. Tuttavia, l'integrazione di strategie di riduzione della complessità (CPA e CAF) con solutori ibridi quantistico-classici rappresenta la via più promettente per l'applicazione pratica del TSP.

• Significato Pratico: Il framework proposto colma il divario tra la teoria dell'ottimizzazione quantistica e le applicazioni pratiche, permettendo di risolvere istanze di dimensioni significative che prima erano fuori portata per i soli metodi quantistici.
• Implicazioni Future: I risultati suggeriscono che, mentre l'hardware quantistico matura, le strategie ibride e le tecniche di preprocessing avanzate saranno cruciali per sfruttare appieno i vantaggi quantistici nell'ottimizzazione combinatoria. Il lavoro apre la strada a future ricerche su strategie di codifica più avanzate e tecniche di decomposizione adattiva.