Sintesi Tecnica: Forge: Rappresentazioni di Ottimizzazione Fondamentali da Embedding di Grafi

1. Definizione del Problema

I problemi di ottimizzazione combinatoria (CO), in particolare la Programmazione Lineare Intera Mista (MIP), sono fondamentali per la scienza e l'ingegneria ma rimangono computazionalmente costosi da risolvere. Sebbene l'apprendimento automatico (ML) offra alternative promettenti, gli attuali approcci basati sull'apprendimento soffrono di significativi limiti di scalabilità e generalizzazione:

• Dipendenza dai Dati: L'addestramento richiede tipicamente la risoluzione di un gran numero di istanze difficili per generare dati etichettati, comportando elevati costi computazionali e dipendendo dagli stessi solver che i ricercatori intendono accelerare.
• Mancanza di Generalizzazione: I metodi esistenti spesso addestrano modelli dedicati per specifiche distribuzioni di problemi, compiti downstream o dimensioni del problema. Essi non riescono a generalizzare tra diversi domini di problemi (ad es. Set Cover vs. Combinatorial Auction) o tipi di task (ad es. generazione di tagli o guida alla ricerca).
• Limitazioni Strutturali: La maggior parte dei metodi CO si affida alle Reti Neurali a Grafo (GNN) che catturano efficacemente le informazioni locali variabile-vincolo, ma faticano a codificare una struttura globale significativa dell'istanza a causa dell'intrinseca località del bias.

Il documento postula la necessità di una rappresentazione di ottimizzazione fondamentale: un modello pre-addestrato, general-purpose, capace di generare embedding MIP che generalizzino attraverso task, problemi e dimensioni, addestrato in modo non supervisionato senza richiedere soluzioni ottimali.

2. Metodologia: Il Framework Forge

Forge (Foundational Optimization Representations from Graph Embeddings) è un framework che pre-addestra un autoencoder di grafi vettorialmente quantizzato su una collezione diversificata di istanze MIP. Si ispira ai modelli fondazionali del Natural Language Processing (NLP) e della Computer Vision (CV).

Architettura Core

Il framework opera attraverso le seguenti fasi (Figura 1):

1. MIP-to-BP (Rappresentazione Bipartita): Le istanze MIP sono rappresentate come grafi bipartiti dove i nodi sono variabili e vincoli.
   • Caratteristiche dei Nodi: A differenza dei lavori precedenti che si affidano a feature generate dal solver (ad es. dagli alberi branch-and-bound), Forge utilizza solo proprietà di input di base: senso del vincolo (>, <, =) e valori RHS per i vincoli; tipo di variabile, limiti e coefficienti dell'obiettivo per le variabili. Ciò garantisce che il modello non dipenda dalla risoluzione dell'istanza.
2. BP-to-GNN: Una GNN basata su GraphSAGE (due livelli) elabora il grafo bipartito per generare embedding continui per ogni nodo.
3. Vector Quantized Codebook (Il "Vocabolario"): Per affrontare l'incapacità della GNN di catturare la struttura globale, gli embedding continui passano attraverso un vettore quantizzatore. Questo mappa ogni nodo a un codice discreto da un codebook apprendibile di dimensione $k$ (che funge da vocabolario).
   • Questo passaggio preserva l'informazione strutturale globale creando una distribuzione di codici discreti attraverso l'istanza, analogamente alla distribuzione dei token nei modelli linguistici.
4. Ricostruzione (Autoencoder): I codici discreti vengono mappati nuovamente in codewords e passati attraverso decoder per ricostruire le caratteristiche originali dei nodi e i pesi degli archi.
5. Funzione di Perdita: Il modello è addestrato in modo non supervisionato per minimizzare:
   • Perdita di ricostruzione (caratteristiche dei nodi e archi).
   • Perdita del codebook (spostamento dei codewords verso gli embedding).
   • Perdita di commitment (spostamento degli embedding verso i codewords).

Rappresentazioni

Una volta addestrato, Forge produce due livelli di rappresentazioni:

• Locale: Codewords discrete per singole variabili e vincoli.
• Globale: Un embedding a livello di istanza derivato dalla distribuzione di frequenza dei codici assegnati attraverso l'intero grafo. La dimensione dell'embedding è uguale alla dimensione del vocabolario ($|codebook|$).

3. Contributi Chiave

Il documento delinea cinque contributi primari:

1. Passaggio ai Modelli Fondazionali: Introduzione di Forge, un singolo modello pre-addestrato che genera embedding MIP sia a livello di istanza che fine-grained (variabile/vincolo) senza supervisione.
2. Generalizzazione Non Supervisionata: Dimostrazione che gli embedding di Forge possono raggruppare (clustering) istanze inedite attraverso diversi domini di problemi e livelli di difficoltà con alta accuratezza, superando le feature statiche e i readout GNN standard.
3. Adattabilità Supervisionata: Prova che lo stesso modello pre-addestrato può essere perfezionato (fine-tuning) con dati minimi e a basso costo per compiti radicalmente diversi (predizione del gap di interezza e guida alla ricerca) attraverso varie dimensioni di problemi.
4. Integrazione con i Solver: Integrazione riuscita delle predizioni di Forge in Gurobi, un solver commerciale, dimostrando miglioramenti consistenti nei gap primari su molteplici tipi di problemi.
5. Augmentation ML: Potenziamento di metodi di apprendimento basati su ML allo stato dell'arte (specificamente Li et al., 2025 e PS-Gurobi) concatenando gli embedding di Forge, ottenendo guadagni di performance significativi su istanze inedite.

4. Risultati Sperimentali

Clustering Non Supervisionato

• Setup: Addestrato su 1.800 istanze MIPLIB; testato su 1.000 istanze inedite da D-MIPLIB e strIPlib coprendo 21 coppie dominio-difficoltà.
• Metrica: Informazione Mutua Normalizzata (NMI) per l'accuratezza del clustering.
• Performance: Forge ha raggiunto un NMI di 0,953, superando significativamente il Mean Readout (0,726) e il Label Propagation (0,790). Le visualizzazioni (PaCMAP) hanno mostrato cluster distinti per ogni tipo di problema e un chiaro gradiente da facile a difficile, nonostante il modello non avesse mai visto queste specifiche istanze durante l'addestramento.

Task I: Predizione del Gap di Interezza (Generazione di Pseudo-Tagli)

• Obiettivo: Predire il gap di interezza per generare un pseudo-taglio per il nodo radice, stringendo il limite della rilassazione LP.
• Addestramento: Fine-tuning su 450 istanze (CA, SC, GIS) con etichette generate da Gurobi (timeout di 120s), evitando la piena ottimalità.
• Risultati:
  • Su istanze di test "molto difficili" (inclusi MVC, che non era presente nel fine-tuning), Forge ha ottenuto deviazioni assolute medie del 12–19% tra i vari tipi di problemi.
  • Impatto sul Solver: L'integrazione dei pseudo-tagli di Forge in Gurobi ha ridotto il gap primario fino all'85% (ad es. guadagno dell'84,52% su Generalized Independent Set) rispetto a Gurovi da solo.
  • Confronto: Ha superato il metodo SOTA di Li et al. (2025) (18,63% di deviazione vs. 20,14%) su 17.500 istanze inedite senza ulteriore addestramento.

Task II: Guida alla Ricerca

• Obiettivo: Predire quali variabili sono probabilmente presenti nella soluzione ottima per guidare la ricerca branch-and-bound.
• Addestramento: Fine-tuning su 700 istanze utilizzando una combinazione di Binary Cross-Entropy (BCE) e Triplet Loss. Le etichette sono state derivate da soluzioni ammissibili trovate entro 5 minuti (nessuna ottimalità richiesta).
• Risultati:
  • Impatto sul Solver: Gurobi con la guida alla ricerca di Forge ha ottenuto fino al 48,75% di miglioramento nel gap primario e fino al 35% di velocizzazione nella convergenza su istanze medie.
  • Augmentation ML: Quando utilizzato per potenziare PS-Gurobi (un metodo di guida alla ricerca basato su ML allo stato dell'arte), gli embedding di Forge hanno ridotto il gap primario di oltre il 40% (Combinatorial Auction) e del 50% (Generalized Independent Set).

5. Significato e Rivendicazioni

Il documento afferma che Forge rappresenta un passo significativo verso i modelli fondazionali per l'ottimizzazione. Il suo significato risiede in:

• Rottura della Dipendenza dal Solver: Impara rappresentazioni strutturali senza richiedere l'accesso a soluzioni ottime o stati interni del solver durante il pre-addestramento, affrontando il problema dell' "uovo e la gallina" del bisogno di solver per addestrare i solver.
• Rappresentazione Universale: Dimostra che un singolo modello può generalizzare attraverso disparati tipi di problemi (ad es. Set Cover, Combinatorial Auction, Vertex Cover) e tipi di task (predizione del gap, guida alla ricerca), una capacità precedentemente limitata a modelli specifici per problema o task.
• Utilità Pratica: Il framework non è meramente teorico; si integra direttamente con i solver commerciali e migliora i pipeline ML esistenti, offrendo guadagni immediati e misurabili nell'efficienza di risoluzione.
• Scienza Aperta: Gli autori rilasciano il codice di addestramento, i pesi pre-addestrati e gli embedding per promuovere ulteriormente la ricerca nel campo della rappresentazione dell'apprendimento.

Gli autori rimangono modesti riguardo ai limiti, notando che l'attuale scala (3,25 milioni di parametri) è piccola rispetto ad altri modelli fondazionali, la semantica del "vocabolario" appreso è inesplorata, e le attuali integrazioni sono "one-shot" piuttosto che iterative durante l'albero branch-and-bound. Suggeriscono che il lavoro futuro possa estendere questi principi ai Problemi di Soddisfacimento di Vincoli (CSP) e SAT.