Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Riepilogo Tecnico: Formulazione a Reti Tensoriali del Problema del Commesso Viaggiatore e Varianti

Definizione del Problema
Il documento affronta il Problema del Commesso Viaggiatore (TSP) e diverse sue generalizzazioni, inclusi il TSP dipendente dal tempo (TDTSP), il Problema di Riassegnazione dei Lavori (JRP) e varianti che coinvolgono vincoli di non ripetizione, regole di precedenza, vincoli di gruppo e obiettivi di collo di bottiglia. Il TSP è definito come la ricerca del percorso più breve che visita esattamente una volta $N$ nodi e ritorna all'origine, un problema noto come NP-difficile. Sebbene esistano algoritmi esatti come Held-Karp ($O(N^2 2^N)$) e branch-and-bound, questi affrontano una complessità esponenziale che ne limita la scalabilità per casi industriali. Al contrario, le euristiche (ad esempio, algoritmi genetici, ricerca locale) offrono soluzioni approssimate senza garanzie di ottimalità. Gli autori osservano che i nascenti algoritmi quantistici (QAOA, VQE) sono attualmente limitati dal rumore hardware (era NISQ), motivando l'esplorazione di tecniche classiche che mimano le proprietà dei sistemi quantistici.

Metodologia
Il contributo principale è una formulazione a reti tensoriali (TN) che rappresenta i tour candidati come stati in uno spazio prodotto tensoriale. Il metodo opera attraverso tre meccanismi principali:

1. Costruzione della Rete Tensoriale:

   • Inizializzazione ('+'): Crea una sovrapposizione uniforme di tutte le possibili assegnazioni di nodi per ogni passo temporale.
   • Ottimizzazione ('S'): Applica un operatore di evoluzione nel tempo immaginario $U = e^{-\tau C(\vec{y})}$, dove $\tau$ è un fattore di smorzamento e $C(\vec{y})$ è il costo del tour. Questo sopprime esponenzialmente le configurazioni ad alto costo, analogamente alla ricerca dello stato fondamentale nei sistemi quantistici.
   • Filtraggio dei Vincoli ('F'): Introduce strati di Operatore Prodotto Matriciale (MPO) per imporre i vincoli. Per il TSP standard, questi strati agiscono come filtri di conteggio che garantiscono che ogni nodo appaia esattamente una volta. I filtri utilizzano indici di legame binari per tracciare se un nodo specifico è stato visitato, implementando efficacemente il vincolo del simbolo di Levi-Civita $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$.
   • Estrazione ('+'): Uno strato di traccia somma le ampiezze per produrre pesi marginali.

2. Estrazione Sequenziale delle Marginali:
   La soluzione viene estratta iterativamente. Per un prefisso fisso del tour, l'algoritmo calcola il peso marginale $Z_p(a; \tau)$ per ogni nodo candidato $a$ nella posizione successiva. Nel limite di $\tau \to \infty$ e aritmetica esatta, il nodo che massimizza questo peso è garantito far parte di un tour ottimale (Proposizione 3.2). L'algoritmo seleziona il nodo massimizzante, aggiorna il prefisso e ripete fino al completamento del tour.

3. Generalizzazioni:
   Il framework è adattato per varie varianti del TSP modificando gli strati di filtro e di evoluzione:

   • DNSNN (Numero Diverso di Passi/Nodi): I filtri permettono ai nodi di apparire tra $N^0$ e $N^f$ volte.
   • NMTSP (Non-Markoviano): Utilizza MPO di ordine superiore per gestire costi dipendenti dai $K$ passi precedenti.
   • BTSP (Collo di Bottiglia): Sostituisce l'evoluzione del costo con uno strato che traccia il costo massimo dell'arco incontrato.
   • PTSP (Vincolato per Gruppi): I filtri impongono la visita di esattamente un nodo per classe.
   • TSPP (Precedenza): Proiettori locali sopprimono i nodi se i loro predecessori richiesti non sono ancora apparsi.
   • JRP (Riassegnazione dei Lavori): Modellato come un problema di assegnazione lineare in cui uno stato "nessun movimento" è ripetibile e specifiche vacanze sono uniche.

4. Approssimazione e Complessità:
   La contrazione esatta dell'intera rete tensoriale è esponenziale, con scala $O(\hat{N}^4 2^{\hat{N}})$ per la contrazione strato per strato densa. Per affrontare istanze più grandi, gli autori propongono:

   • Ablazione degli Strati: Applicare solo un sottoinsieme degli strati di vincolo per ridurre la complessità, trattando il risultato come euristica.
   • Contrazione Sparsa-Locale: Sfruttare la natura deterministica e sparsa dei tensori di filtro locali per ridurre i prefissi polinomiali (ad esempio, da $O(\hat{N}^4 2^{\hat{N}})$ a $O(\hat{N}^3 2^{\hat{N}})$) senza cambiare la scala esponenziale.
   • Euristica a $\tau$ Finito: Utilizzare precisione finita e $\tau$ finito per approssimare il limite a temperatura zero, riconoscendo che il contrasto numerico e le degenerazioni influenzano la qualità della soluzione.

Contributi Chiave

• Formula Marginale Esplicita: Derivazione di un'equazione marginale a rete tensoriale il cui limite a temperatura zero e aritmetica esatta identifica un tour fattibile ottimale tramite una regola marginale sequenziale.
• Codifica dei Vincoli: Definizione di strati MPO per vincoli di conteggio (non ripetizione) applicabili a vari problemi combinatori.
• Framework di Generalizzazione: Una costruzione modulare che adatta il formalismo TN alle varianti del TSP (TDTSP, JRP, BTSP, ecc.) alterando specifici strati tensoriali.
• Implementazione Euristica: Un'implementazione a precisione finita e $\tau$ finito che funziona come euristica calibrata, con un'analisi del suo comportamento riguardo al contrasto numerico e alle degenerazioni.

Risultati
Lo studio sperimentale si concentra su piccole istanze sintetiche ($N \in \{5, \dots, 12\}$) per validare la correttezza del metodo e il comportamento numerico piuttosto che per rivendicare superiorità computazionale rispetto a solver specializzati.

• Calibrazione: Il parametro di tempo immaginario $\tau$ dipende dalla dimensione. Una scansione di calibrazione ($\tau \in \{1, \dots, 40\}$) ha migliorato significativamente il tasso di soluzione ottimale dal 55,56% (a $\tau=1$) al 95,56% sul set di valutazione.
• Confronto con Solver: Su piccole istanze, il solver TN calibrato ha raggiunto un tasso di ottimalità del 95,24%, superando NetworkX greedy (26,67%) e simulated annealing (59,05%), ma rimanendo al di sotto del riferimento esatto Held-Karp (100%).
• Ablazione degli Strati: La rimozione degli strati di vincolo ha degradato la qualità della soluzione, confermando che l'insieme completo dei filtri è necessario per un'alta accuratezza.
• Caso Industriale (JRP): In una prova di concetto per il Problema di Riassegnazione dei Lavori ONCE, il metodo TN ha prodotto soluzioni con costi accumulati identici a quelli dell'Azure Digital Annealer, differendo solo in casi degeneri in cui esistono molteplici assegnazioni ottimali.

Significato e Affermazioni
Gli autori dichiarano esplicitamente modestia riguardo alla potenza computazionale del metodo. Non rivendicano un vantaggio computazionale generale rispetto a solver classici specializzati (come Held-Karp, branch-and-cut o algoritmi specifici per l'assegnazione) per il TSP generale.

• Rappresentazione Formale: Il lavoro è presentato come una "rappresentazione formale esatta in aritmetica a tempo esponenziale" e una "piattaforma per approssimazioni ed estensioni controllate".
• Natura Euristica: L'implementazione a $\tau$ finito è caratterizzata come un'"euristica calibrata a precisione finita" il cui comportamento dipende dal contrasto numerico e dalle degenerazioni.
• Utilità: Il valore principale risiede nel framework modulare a reti tensoriali, che permette l'integrazione sistematica di vincoli diversi (precedenza, gruppi, costi non markoviani) e l'applicazione di tecniche di approssimazione (rimozione degli strati, contrazioni sparse) all'interno di un formalismo unificato.
• Limitazioni: Il metodo mantiene una scala esponenziale nel caso peggiore. Problemi di stabilità numerica (underflow, perdita di contrasto in casi degeneri) e la necessità di una calibrazione dipendente dalla dimensione sono identificati come limitazioni significative.

In sintesi, il documento fornisce un formalismo rigoroso a reti tensoriali per il TSP e le sue varianti, dimostrando la sua capacità di recuperare soluzioni ottimali su piccole istanze e integrare vincoli industriali, pur riconoscendo che non supera la complessità esponenziale fondamentale del problema.