Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Sintesi Tecnica: Ricerca del Vicinato Ampio assistita da Macchine Ising con Dimensione del Sottoproblema Flessibilmente Regolabile

Enunciato del Problema
Le macchine Ising fungono da risolutori euristici per l'ottimizzazione combinatoria ricercando stati a bassa energia di modelli Ising o di Ottimizzazione Binaria Non Vincolata Quadratica (QUBO). Tuttavia, l'applicazione diretta di queste macchine a problemi vincolati su larga scala (il "metodo ingenuo") affronta due difficoltà primarie:

1. Scalabilità: Il numero di variabili binarie nella formulazione QUBO spesso supera la capacità hardware delle attuali macchine Ising.
2. Fattibilità: I vincoli vengono tipicamente incorporati come termini di penalità. Di conseguenza, lo spazio di ricerca include soluzioni non ammissibili, e gli stati a bassa energia non corrispondono necessariamente a soluzioni ammissibili di alta qualità per il problema originale.

Sebbene gli approcci esistenti come il fissaggio delle variabili o il divide-and-conquer tentino di ridurre le dimensioni del problema, essi spesso faticano a bilanciare la dimensione del sottoproblema con la capacità di ricostruire soluzioni ammissibili per il problema originale. La Ricerca del Vicinato Ampio (Large Neighborhood Search - LNS) offre un framework in cui una soluzione ammissibile corrente viene iterativamente migliorata ri-ottimizzando un sottoproblema (un "vicinato"). Mentre l'LNS preserva la fattibilità se il metodo di generazione del sottoproblema è progettato correttamente, le prestazioni dell'LNS assistito da macchina Ising sono altamente sensibili alla dimensione del sottoproblema. Se il sottoproblema è troppo piccolo, il potenziale miglioramento per iterazione è limitato; se è troppo grande, la qualità della soluzione della macchina Ising degrada a causa dell'espansione dello spazio di ricerca.

Metodologia
Il documento si concentra su due problemi: il Problema del Trasporto Veicolare (VRP) e il Problema del Multicontenitore Quadratico (QMKP).

• Metodo Esistente (LNS-V): Per il VRP, gli autori analizzano un precedente metodo (LNS-V) che seleziona un sottoinsieme di veicoli e ri-ottimizza l'intero percorso di ciascuno. Sebbene ciò preservi la fattibilità, la dimensione del sottoproblema è controllata esclusivamente dal numero di veicoli selezionati ($V'$). Poiché l'intero percorso di un veicolo selezionato viene ri-ottimizzato, il numero di variabili scala come $(V')^2(T-2)^2$ (dove $T$ è il numero totale di step). Ciò risulta in una granularità grossolana; cambiare $V'$ di una unità può causare un salto massiccio nel conteggio delle variabili, rendendo difficile regolare la dimensione del sottoproblema nell'intervallo ottimale per la macchina Ising.

• Metodo Proposto (LNS-VT): Per affrontare il problema della granularità, gli autori propongono LNS-VT. Oltre a selezionare $V'$ veicoli, LNS-VT introduce un nuovo parametro: il numero di passi consecutivi ($T'$) da ri-ottimizzare per ogni veicolo selezionato.

  • Meccanismo: Per ogni veicolo selezionato, viene estratto un segmento contiguo del percorso (di lunghezza $T_{seg} = \min(T', \text{step validi effettivi})$). Il sottoproblema ri-ottimizza l'assegnazione e l'ordine dei siti all'interno di questi specifici segmenti, mantenendo fisso il resto del percorso.
  • Fattibilità: Fissando i siti al di fuori degli intervalli di estrazione e garantendo che i segmenti estratti coinvolgano solo siti non-deposito, il metodo garantisce che la reinserimento di qualsiasi soluzione ammissibile del sottoproblema produca una soluzione ammissibile per l'originale VRP.
  • Controllo delle Variabili: Il numero di variabili libere in LNS-VT è approssimativamente $(V'T')^2$. Ciò consente un controllo fine-grained sulla dimensione del sottoproblema indipendentemente dal numero totale di step del problema $T$.

• Estensione al QMKP: Gli autori applicano lo stesso principio di progettazione al QMKP. Costruiscono un metodo di generazione del sottoproblema che seleziona un sottoinsieme di contenitori ($K'$) e un sottoinsieme di articoli ($N'$) da ri-ottimizzare. Questo metodo preserva la fattibilità fissando gli articoli non inclusi nel set selezionato e regolando i vincoli di capacità per la capacità residua dei contenitori selezionati.

Risultati Chiave
Esperimenti numerici sono stati condotti su un VRP con 300 siti e 5 veicoli e un QMKP con 200 articoli e 5 contenitori, utilizzando la macchina Ising Fixstars Amplify AE.

• Prestazioni VRP:

  • L'LNS-VT ha superato sia il metodo ingenuo che l'esistente LNS-V.
  • La migliore impostazione LNS-VT (specificamente $V'=2, T'=40$) ha ridotto il valore obiettivo di circa il 10% rispetto a LNS-V dopo 100 iterazioni.
  • LNS-VT ha raggiunto la qualità della soluzione finale di LNS-V utilizzando solo circa il 30% delle iterazioni.
  • Sensibilità delle Variabili: L'intervallo ottimale del sottoproblema (in termini di variabili di assegnazione dei siti non-deposito) è stato individuato tra 6.000 e 10.000. L'esistente LNS-V non poteva raggiungere questo intervallo con $V' \ge 2$ (il suo minimo era di circa 14.400 variabili), spiegando la sua prestazione inferiore.
  • Necessità Dinamiche: La dimensione appropriata del sottoproblema cambiava durante il processo di ricerca. Sottoproblemi più grandi erano più efficaci nelle prime iterazioni (valori obiettivi elevati), mentre sottoproblemi più piccoli erano più efficenti nelle iterazioni successive (per raffinare le soluzioni di alta qualità).

• Prestazioni QMKP:

  • L'LNS applicato al QMKP ha anch'esso superato il metodo ingenuo.
  • La dimensione ottimale del sottoproblema per il QMKP è risultata essere significativamente più piccola, circa 100 a 150 variabili.
  • Questa marcata differenza rispetto al VRP (6.000–10.000) indica che la dimensione ottimale del sottoproblema dipende dalla specifica classe di problemi e dalla formulazione QUBO, non solo dalle capacità della macchina Ising.

Significatività e Rivendicazioni
Il documento sostiene che, affinché l'LNS assistito da macchina Ising sia efficace per problemi vincolati su larga scala, la sola preservazione della fattibilità è insufficiente. La capacità di regolare in modo flessibile la dimensione del sottoproblema per farla coincidere con il punto di massima efficienza della macchina Ising è un fattore di design critico.

Lo studio dimostra che:

1. L'introduzione di un parametro di controllo aggiuntivo (passi consecutivi per il VRP, o conteggi di articoli/contenitori per il QMKP) permette un aggiustamento fine-grained della dimensione del sottoproblema, cosa impossibile con i metodi che variano solo il numero di entità selezionate.
2. Esiste un intervallo ottimale di variabili per il sottoproblema che massimizza la qualità della soluzione, e tale intervallo varia significativamente tra diverse classi di problemi (VRP vs. QMKP).
3. La dimensione ottimale del sottoproblema può anche dipendere dalla qualità della soluzione corrente, suggerendo che le impostazioni di parametri statici potrebbero non essere ottimali durante l'intero processo di ricerca.

Gli autori concludono che, sebbene i loro risultati siano specifici per le istanze e le impostazioni della macchina testate, il principio della generazione di sottoproblemi strutturati e flessibilmente regolabili è una direzione promettente per l'ottimizzazione combinatoria vincolata. Notano che il lavoro futuro dovrebbe concentrarsi sullo sviluppo di strategie adattive per selezionare automaticamente i parametri del sottoproblema in base alla fase di ricerca e alla struttura del problema.