Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Sintesi Tecnica: Caratteristiche Geometriche dei Sottoproblemi in una Ricerca di Vicinato Ampio assistita da Macchine Ising

Definizione del Problema
Problemi di ottimizzazione combinatoria vincolata su larga scala, come il Problema del Veicolo Singolo (VRP), richiedono spesso formulazioni QUBO (Quadratic Unconstrained Binary Optimization) che superano i limiti di dimensione di input delle attuali macchine Ising o che soffrono di una degradazione della qualità della soluzione all'aumentare del numero di variabili binarie. Sebbene la Ricerca di Vicinato Ampio (LNS - Large Neighborhood Search) mitighi questo problema ottimizzando sequenzialmente sottoproblemi ristretti, gli approcci esistenti trattano principalmente il numero di variabili binarie come l'unico parametro di controllo. Gli autori sostengono che il numero di variabili da solo sia insufficiente per caratterizzare un sottoproblema; diverse regole di costruzione possono generare strutture interne, relazioni di vincolo e distribuzioni geometriche distinte, anche a parità di numero di variabili. La domanda centrale è se la regola di costruzione del sottoproblema influenzi il processo di ottimizzazione sequenziale quando la dimensione del sottoproblema (numero di variabili binarie) viene mantenuta costante.

Metodologia
Lo studio investiga questa questione utilizzando il VRP come banco di prova, confrontando due distinte regole di costruzione dei sottoproblemi all'interno di un framework LNS assistito da macchine Ising:

1. LNS-K (Basata sulla Struttura dei Percorsi): Questo metodo costruisce i sottoproblemi basandosi sulle unità semantiche del VRP. Seleziona un sottoinsieme di veicoli ($K'$) dalla soluzione corrente e include tutti i clienti visitati da tali veicoli. Le variabili del sottoproblema corrispondono ai percorsi dei veicoli selezionati e ai loro clienti associati.
2. LNS-Q (Basata sulle Variabili QUBO): Questo metodo costruisce i sottoproblemi basandosi sulla rappresentazione QUBO. Seleziona un sottoinsieme di variabili binarie attive ($n'$) dalla soluzione corrente come "ancore" e include tutte le variabili coinvolte nei vincoli associati a queste ancore. Questo approccio opera a livello di rappresentazione piuttosto che a livello di dominio del problema.

Gli autori hanno utilizzato due macchine Ising: la D-Wave Advantage 4.1 (quantum annealing) per istanze di piccola scala ($N=5, 6, 7$) e la Fixstars Amplify AE (basata su GPU) per istanze di grande scala ($N=100, 200, 300, 400$).

Il protocollo sperimentale ha previsto due confronti principali:

• LNS vs Approccio Naive: Confronto tra la LNS sequenziale e una sottomissione singola (single-shot) dell'intero QUBO, pareggiata per tempo di annealing totale.
• LNS-K vs LNS-Q: Un confronto a "dimensione corrispondente" (matched-size) in cui i parametri $K'$ e $n'$ sono stati calibrati affinché entrambi i metodi generassero sottoproblemi con lo stesso identico numero di variabili binarie.

Le metriche chiave includevano la distanza totale della soluzione, la traiettoria di miglioramento iterativo e la varianza di posizione del set di clienti selezionati (una misura della diffusione spaziale dei clienti inclusi nel sottoproblema).

Risultati Chiave

1. Efficacia dell'Ottimizzazione Sequenziale: Sotto budget di tempo di annealing totale equivalenti, la LNS ha costantemente superato l'approccio naive (singolo QUBO completo) su entrambe le piattaforme hardware e dimensioni dei problemi. La LNS ha mantenuto soluzioni fattibili durante tutto il processo e ha raggiunto distanze totali significativamente più brevi, in particolare per le istanze più grandi ($N=400$).
2. Impatto delle Regole di Costruzione: Anche quando il numero di variabili binarie nei sottoproblemi era strettamente pareggiato, LNS-K e LNS-Q hanno mostrato comportamenti di ottimizzazione differenti.
   • Qualità della Soluzione Finale: LNS-K ha ottenuto distanze totali finali più brevi rispetto a LNS-Q attraverso l'intero intervallo di parametri testati per l'istanza con 400 clienti.
   • Traiettorie Iterative: LNS-K ha dimostrato un miglioramento iterativo più rapido, in particolare per dimensioni di sottoproblema corrispondenti più piccole ($K'=2, 3$).
3. Evoluzione Geometrica: Una scoperta critica riguarda la distribuzione spaziale dei clienti selezionati.
   • In LNS-K, la varianza di posizione del set di clienti selezionati è diminuita significativamente durante le iterazioni, indicando che l'algoritmo si è concentrato progressivamente su cluster di clienti più localizzati spazialmente man mano che la soluzione migliorava.
   • In LNS-Q, la varianza di posizione è rimasta quasi costante durante le iterazioni, indipendentemente dalla dimensione del sottoproblema.

Significatività e Rivendicazioni
L'articolo sostiene che il numero di variabili binarie sia un descrittore insufficiente per i sottoproblemi nell'ottimizzazione sequenziale assistita da macchine Ising. Lo studio dimostra che la regola di costruzione stessa — specificamente, se le variabili sono raggruppate per unità semantiche del dominio del problema (percorsi) o per relazioni di vincolo QUBO — modella fondamentalmente la traiettoria di ottimizzazione e la qualità della soluzione finale.

Gli autori sostengono che la progettazione dei sottoproblemi debba considerare non solo la dimensione, ma anche le strutture semantiche e geometriche ereditate dalla soluzione corrente. La superiorità delle prestazioni di LNS-K suggerisce che preservare la struttura dei percorsi della soluzione corrente permetta all'algoritmo di sfruttare la località spaziale, portando a riorganizzazioni locali più efficaci.

Limitazioni e Ambito
Gli autori notano esplicitamente alcune limitazioni:

• Le conclusioni sono specifiche per le istanze VRP testate e per la particolare formulazione QUBO utilizzata.
• L'analisi geometrica è descrittiva; l'articolo non stabilisce un legame causale tra la diminuzione della varianza di posizione e il miglioramento della distanza totale, né afferma che la localizzazione spaziale sia l'unica causa del successo di LNS-K.
• Il confronto dettagliato della struttura è stato eseguito principalmente sulla piattaforma Fixstars Amplify AE; i risultati non sono dichiarati come indipendenti dall'hardware.
• Lo studio non fornisce un benchmark esaustivo contro le euristiche classiche di routing dei veicoli allo stato dell'arte, concentrandosi invece sulle dinamiche interne della LNS assistita da macchine Ising.

In conclusione, l'articolo postula che la progettazione efficace dei sottoproblemi per le macchine Ising richieda l'integrazione delle informazioni strutturali dalla soluzione corrente, andando oltre i semplici vincoli del conteggio delle variabili.