Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Sintesi Tecnica: Valutazione delle Prestazioni delle Formulazioni Dirette di Ordine Superiore nei Problemi di Ottimizzazione Combinatoria

Enunciato del Problema
I problemi di ottimizzazione combinatoria si riscontrano frequentemente in campi quali la logistica, la progettazione di materiali e l'ottimizzazione del portafoglio. Sebbene molti di questi problemi siano NP-hard e richiedano approcci euristici, esiste una barriera significativa nella loro implementazione su "macchine Ising" (inclusi l'hardware di quantum annealing e i solver ispirati alla fisica). La maggior parte delle piattaforme hardware esistenti accetta input esclusivamente nel formato QUBO (Quadratic Unconstrained Binary Optimization), il che limita le funzioni obiettivo a termini lineari e quadratici di variabili binarie.

Tuttavia, numerosi problemi del mondo reale, come il campionamento di polimeri, il ripiegamento delle proteine e specifici compiti di routing, comportano intrinsecamente interazioni di ordine superiore (cubiche, quartiche, ecc.). Per risolverli su hardware standard, i ricercatori devono applicare tecniche di "riduzione dell'ordine" per trasformare i problemi PUBO (Polynomial Unconstrained Binary Optimization) in forma QUBO. Questo processo introduce variabili ausiliarie e termini di penalità per mantenere la coerenza logica. Gli autori sostengono che questa trasformazione aumenta inevitamente la dimensione del problema e la complessità strutturale, potenzialmente degradando la qualità e la stabilità della soluzione, eppure l'impatto specifico del trattamento diretto dei termini di ordine superiore rispetto alla loro riduzione non è stato ancora quantificato accuratamente su una piattaforma unificata per istanze pratiche di larga scala.

Metodologia
Per affrontare questa lacuna, lo studio impiega un framework di valutazione comparativa utilizzando l'Fixstars Amplify Annealing Engine (Amplify AE). Questo solver ad alte prestazioni, basato sul Simulated Annealing (SA) e sulla parallelizzazione su larga scala tramite GPU, offre due modalità distinte:

1. Solver PUBO: Ottimizza direttamente funzioni obiettivo contenenti termini fino al quarto ordine senza modifiche.
2. Solver QUBO: Risolve gli stessi problemi dopo l'applicazione del metodo di sostituzione per la riduzione dell'ordine. Questo metodo sostituisce i prodotti di variabili binarie con nuove variabili ausiliarie e impone vincoli tramite termini di penalità (specificamente, $x_1x_2 = y_{1,2}$).

Lo studio confronta entrambi gli approcci su due problemi benchmark che contengono naturalmente termini di ordine superiore:

• Low Autocorrelation Binary Sequence (LABS): Un problema che cerca sequenze binarie con minima energia di autocorrelazione. La funzione di energia coinvolge termini di autocorrelazione al quadrato, risultando in interazioni di quarto ordine ($s_i s_{i+k} s_j s_{j+k}$).
• Vehicle Routing Problem (VRP) con Bilanciamento delle Distanze: Un problema multi-obiettivo che minimizza la distanza totale di viaggio minimizzando simultaneamente la varianza delle distanze tra i veicoli. Il termine di varianza introduce interazioni di quarto ordine quando viene espanso.

Gli esperimenti sono stati condotti con tempi computazionali fissi (60 secondi) attraverso varie dimensioni del problema. Per LABS, le lunghezze delle sequenze ($N$) variavano da 5 a 99. Per il VRP, il numero di posizioni dei clienti ($P$) e di veicoli ($V$) è stato variato. Il solver QUBO ha utilizzato un coefficiente di penalità fisso ($p=1$) per il metodo di sostituzione, mentre il solver PUBO non ha richiesto tale parametro di sintonizzazione.

Contributi Chiave e Risultati
Il documento fornisce un'analisi quantitativa dei compromessi tra la formulazione diretta PUBO e la formulazione ridotta QUBO:

1. Qualità della Soluzione e Stabilità:

   • LABS: Il solver PUBO ha ottenuto costantemente valori di energia normalizzata inferiori (più vicini alla soluzione ottimale) con deviazioni standard significativamente minori rispetto al solver QUBO. Il divario di prestazione si è ampliato all'aumentare della lunghezza della sequenza $N$.
   • VRP: In un'analisi su singola istanza, il solver PUBO ha prodotto scambi più stabili tra distanza totale e varianza della distanza. I grafici a dispersione hanno rivelato che le soluzioni QUBO erano ampiamente disperse e non riuscivano a raggiungere la regione di minima varianza reale, mentre le soluzioni PUBO si concentravano vicino alla frontiera di Pareto.
   • Analisi dell'Ipervolume: Attraverso 30 istanze VRP generate casualmente, il solver PUBO ha ottenuto costantemente indicatori di ipervolume maggiori (una misura della diversità e della qualità dell'insieme di soluzioni) rispetto al solver QUBO, confermando la sua superiorità nell'ottimizzazione multi-obiettivo.

2. Espansione delle Variabili:

   • Lo studio ha quantificato l'"esplosione delle variabili" causata dalla riduzione dell'ordine. Per entrambi i problemi, LABS e VRP, il numero di variabili binarie nella formulazione QUBO è cresciuto rapidamente con la dimensione del problema, raggiungendo decine di volte il numero di variabili della formulazione diretta PUBO per le istanze di grandi dimensioni. Questa espansione amplia lo spazio di ricerca, contribuendo al degrado della stabilità della soluzione osservato.

3. Sensibilità ai Coefficienti di Penalità:

   • Gli autori hanno investigato la sensibilità dell'approccio QUTO al coefficiente di penalità ($p$) utilizzato nel metodo di sostituzione. Un'analisi tramite heatmap per il problema LABS ha dimostrato che il coefficiente di penalità ottimale varia significamente con la dimensione del problema ($N$). Nessun valore singolo di $p$ ha fornito prestazioni consistenti attraverso tutte le scale, evidenziando la difficoltà di sintonizzare le formulazioni ridotte per applicazioni generali.

Significato e Rivendicazioni
Il documento sostiene che la gestione diretta dei termini di ordine superiore tramite formulazioni PUBO offre vantaggi distinti rispetto ai metodi tradizionali di riduzione dell'ordine quando si risolvono problemi di ottimizzazione combinatoria su moderni hardware di tipo Ising. Il significato primario risiede nella dimostrazione che:

• Integrità Strutturale: Preservare la struttura originale del problema (PUFO) evita l'espansione artificiale dello spazio di ricerca causata dalle variabili ausiliarie.
• Robustezza: La formulazione diretta elimina la necessità di sintonizzare i coefficienti di penalità, che sono sensibili alla scala del problema e possono destabilizzare il processo di ricerca.
• Scalabilità: L'approccio PUBO mantiene una qualità e una stabilità della soluzione superiori all'aumentare delle dimensioni del problema, mentre l'approccio QUBO soffre degli effetti cumulativi dell'espansione delle variabili e dell'applicazione dei vincoli.

Gli autori concludono che, sebbene la riduzione dell'ordine sia stata efficace per vari problemi, la formulazione diretta PUBO rappresenta un approccio promettente per scenari di ottimizzazione pratica su larga scala, offrendo sia semplicità strutturale che stabilità computazionale. Lo studio suggerisce che lo sviluppo futuro di hardware e solver debba continuare a supportare l'esecuzione diretta di ordini superiori per sfruttare appieno questi vantaggi nelle applicazioni del mondo reale.