An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization

Riepilogo Tecnico: Una Soglia di Efficienza Ammortizzata per Confrontare Risolutori Neurali ed Euristici nell'Ottimizzazione Combinatoria

Enunciato del Problema
Il documento affronta una critica prevalente nella ricerca operativa e nell'IA Verde: ovvero che i risolutori neurali per l'ottimizzazione combinatoria (CO) siano intrinsecamente meno efficienti dal punto di vista energetico rispetto alle metaeuristiche tradizionali basate su CPU, a causa dei sostanziali costi energetici associati all'addestramento su GPU. Gli autori sostengono che tale critica si fonda su un passaggio inferenziale errato. Essa tratta erroneamente l'elevato costo fisso iniziale dell'addestramento come una squalifica permanente, ignorando il fatto che i risolutori neurali sostengono un costo di inferenza per istanza molto ridotto e ammortizzabile, mentre le metaeuristiche sostengono un costo marginale costante per ogni istanza risolta. Il documento ipotizza che questi due profili di costo (fisso vs marginale) non siano commensurabili come grandezze scalari, ma debbano essere confrontati su un volume specifico di distribuzione.

Metodologia: La Soglia di Efficienza Ammortizzata (AET)
Per formalizzare questo confronto, il documento introduce la Soglia di Efficienza Ammortizzata (AET), un quadro quantitativo definito da tre componenti fondamentali:

1. Definizione di AET: L'AET è il volume di distribuzione ($N$) al quale l'energia cumulativa (o il carbonio) di un risolutore neurale ($M$) eguaglia quella di un risolutore euristico di base ($B$). È calcolata come:
   $$AET = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   Tale calcolo è soggetto a un vincolo di fattibilità della qualità: il gap di ottimalità atteso del risolutore neurale non deve superare il gap della base di più di una tolleranza $\delta$ definita dall'utente. Questo vincolo impedisce a risolutori "veloci ma errati" di abbassare artificialmente la soglia.

   • $E_{train}(M)$ include il costo cumulativo di tutti i saggi di iperparametri, le esecuzioni fallite e i prototipi, non solo il modello finale convergente.
   • $E_{inst}^{NN}$ è l'energia di inferenza per istanza, calcolata in base alla capacità di elaborazione in batch ($\tau_{NN}$) piuttosto che al tempo reale di una singola istanza, riflettendo la natura parallela dell'esecuzione GPU.

2. Contabilità del Ciclo di Vita (Carbonio Incorporato): Il quadro estende la contabilità energetica operativa per includere il carbonio incorporato derivante dalla fabbricazione dell'hardware. Questo costo è ammortizzato linearmente su una vita utile dell'hardware configurabile (predefinita a cinque anni) e applicato simmetricamente sia all'acceleratore neurale che alla CPU di base. Ciò garantisce che il confronto tenga conto dell'impatto dell'intero ciclo di vita, notando che le GPU ad alta capacità di elaborazione possono avere un onere incorporato per istanza inferiore rispetto alle CPU se utilizzate in modo efficiente.

3. Argomento Strutturale Asintotico: Il documento dimostra (Proposizione 1) che se l'energia per istanza del risolutore neurale è strettamente inferiore a quella della base ($E_{inst}^{NN} < E_{inst}^{base}$), il rapporto delle loro energie cumulative converge a una costante strettamente inferiore a uno allorché $N \to \infty$. Crucialmente, questo limite è indipendente dal costo di addestramento, dal sovraccarico del datacenter (PUE) o dall'intensità carbonica regionale, a condizione che questi fattori si applichino simmetricamente a entrambi i lati.

Istantanea Sperimentale e Risultati
Il quadro è istanziato sull'ambiente Multi-Task Vehicle Routing Problem (MTVRP) con $n=20$ clienti attraverso 19 varianti del problema.

• Base di Confronto: Ricerca Genetica Ibrida (HGS) implementata in PyVRP.
• Risolutore Neurale: Una politica appresa addestrata su una singola GPU attraverso cinque semi.
• Metriche Chiave:
  • Rapporto per istanza: Il risolutore neurale consuma circa 0,41 Wh per istanza rispetto a 1,32 Wh per la base HGS monofilo (un guadagno di efficienza di circa 2,4 volte per istanza).
  • Costo di Addestramento: L'energia mediana di addestramento è stata di 121,5 Wh.
  • Punto di Incrocio (AET): L'incrocio misurato avviene a circa $1,58 \times 10^5$ istanze distribuite. Al di sopra di questo volume, il risolutore neurale diventa più efficiente dal punto di vista energetico in termini di energia cumulativa totale.
  • Sensibilità: Gli autori analizzano una superficie di sensibilità a cinque assi (dimensione del batch, tolleranza di qualità, thread di base, livello hardware, seme di addestramento). Essi rilevano che, sebbene il livello hardware e la tolleranza di qualità spostino significativamente il valore dell'AET, la convergenza strutturale del rapporto rimane robusta.

Contributi Chiave

1. Formalizzazione dell'AET: Una metrica che quantifica il punto di pareggio per i risolutori neurali sotto vincoli espliciti di qualità della soluzione, spostando il dibattito da retorico a quantitativo.
2. Correzione del Ciclo di Vita: L'inclusione del carbonio incorporato ammortizzato simmetricamente, sfidando i metodi di contabilità limitati all'operatività.
3. Dimostrazione Asintotica: Una dimostrazione matematica che il verdetto qualitativo (i risolutori neurali vincono su larga scala) è strutturalmente solido e indipendente dalle controversie di calibrazione riguardanti i costi di addestramento o l'intensità della rete elettrica.
4. Strumentazione Aperta: Il rilascio di protocolli di misurazione e script per riprodurre il tracciamento energetico e l'analisi di sensibilità.

Significato e Affermazioni
Il documento afferma di risolvere l'obiezione sull'"efficienza energetica" contro i risolutori neurali per la CO riformulando la domanda. Afferma che l'obiezione è corretta riguardo alla premessa (l'addestramento è costoso) ma errata riguardo alla conclusione (il metodo è complessivamente inefficiente).

• Dipendenza dal Regime: I risolutori neurali sono meno efficienti solo al di sotto dell'AET. Al di sopra dell'AET, il costo marginale dell'euristica si accumula senza limiti, mentre il costo fisso del risolutore neurale è completamente ammortizzato.
• Vantaggio Strutturale: Il documento sostiene che il vantaggio strutturale dell'inferenza neurale in batch rispetto alla ricerca euristica seriale implica che il divario di efficienza si allargherà significativamente a dimensioni del problema più grandi ($n=50, 100$), dove i tempi di ricerca euristica scalano in modo superlineare mentre la capacità di elaborazione neurale rimane relativamente stabile.
• Modestia: Gli autori dichiarano esplicitamente che i risultati attuali sono una "configurazione illustrativa" a $n=20$. Riconoscono che il rapporto per istanza (0,41) è moderato e che la piena validazione empirica della superficie di sensibilità e delle dimensioni del problema più grandi è lasciata a lavori futuri. Il documento non afferma che i risolutori neurali siano universalmente superiori, ma fornisce piuttosto il quadro per determinare quando e in quali condizioni sono la scelta ambientalmente preferibile.