Sintesi Tecnica: EvoOptiGraph

Definizione del Problema

Automatizzare la traduzione di problemi decisionali in linguaggio naturale in modelli di ottimizzazione matematica formale (specificamente, Programmi Lineari Interi Misti, o MILP) rimane una sfida significativa per i Large Language Models (LLM). Gli approcci attuali affrontano due limitazioni primarie:

1. Mancanza di Diversità Strutturale nei Dati di Addestramento: I benchmark esistenti (ad esempio, NL4Opt, MAMO) coprono solo un sottoinsieme ristretto di formulazioni di ottimizzazione valide. Le pipeline di sintesi dei dati si affidano spesso a template fissi con perturbazioni dei parametri, fallendo nel generare la vasta diversità strutturale necessaria per una robusta generalizzazione.
2. Pipeline di Addestramento Statiche: La maggior parte delle configurazioni di addestramento utilizza un dataset congelato costruito prima dell'addestramento del modello. Questo disaccoppiamento impedisce al sistema di identificare i regimi strutturali specifici in cui il modello fallisce e di generare nuovi istanze per colpire tali debolezze.

Metodologia: EvoOptiGraph

Gli autori propongono EvoOptiGraph, un framework di co-evoluzione guidato dalle debolezze che accoppia la generazione dei dati e l'addestramento del modello attraverso una rappresentazione strutturale esplicita. Il framework opera in un ciclo chiuso comprendente tre componenti principali:

1. Rappresentazione Strutturale Basata su Grafi

Ogni MILP è rappresentato come un grafo bipartito attribuito $G = (V, E, A)$:

• Nodi: Un nodo per ogni variabile decisionale ($V_{var}$) e uno per ogni vincolo più un nodo dedicato all'obiettivo ($V_{con}$).
• Archi: Collegano le variabili ai vincoli/obiettivi dove i coefficienti sono non nulli; i pesi degli archi memorizzano i valori dei coefficienti.
• Attributi: I nodi memorizzano metadati come i limiti delle variabili, i tipi (interi/continui/binari), i sensi dei vincoli e i valori del lato destro (RHS).
  Questa rappresentazione consente la compilazione deterministica in codice per solver (ad esempio, Gurobi) e supporta operazioni genetiche che preservano la validità.

2. Generazione di Dati Controllabile tramite Evoluzione dei Grafi

Invece di perturbare testo o parametri, EvoOptiGraph evolve le istanze di ottimizzazione direttamente nello spazio dei grafi utilizzando operatori genetici:

• Crossover: Scambia sottografi compatibili tra istanze genitrici (ad esempio, combinando un vincolo di programmazione della produzione con un vincolo knapsack). È consentito il crossover tra classi diverse per aumentare la diversità strutturale.
• Mutazione: Opera a tre livelli:
  • Parametro: Perturba coefficienti, limiti e valori RHS.
  • Strutturale: Inserisce, elimina o modifica variabili/vincoli preservando la linearità.
  • Scala: Cambia la dimensione del problema (ad esempio, espandendo i nodi di offerta/domanda).
• Funzione di Fitness: I candidati sono valutati in base a:
  • Difficoltà: Derivata dalle statistiche del solver (tempo di risoluzione, nodi branch-and-bound).
  • Diversità: Misurata tramite la Distanza di Edit del Grafo (GED) rispetto alla popolazione corrente.
  • Allineamento con le Debolezze: Similarità del coseno tra le caratteristiche strutturali dell'istanza e il vettore di debolezza attuale del modello.

3. Addestramento del Modello in Due Fasi e Ciclo di Co-evoluzione

Il processo di addestramento alterna l'adattamento del modello all'evoluzione dei dati:

1. Warm-up (SFT): Il LLM di base viene sottoposto a fine-tuning supervisionato su una popolazione iniziale di istanze verificate generate da generatori seed esperti.
2. Analisi delle Debolezze: Il modello corrente viene valutato su un set di validazione tenuto da parte. Un classificatore XGBoost predice il fallimento basandosi su caratteristiche strutturali derivate dal grafo. I valori SHAP vengono calcolati sui casi di errore per generare un vettore di debolezza ($w$) che evidenzia le proprietà strutturali più associate ai fallimenti del modello.
3. Reinforcement Learning con Debolezze (RLVR): Il generatore evolutivo è distorto verso le istanze le cui caratteristiche strutturali si allineano con il vettore di debolezza ($\tilde{f}_{weak}$). Il modello viene quindi aggiornato utilizzando il Reinforcement Learning con Ricompense Verificabili (RLVR).
   • Ricompense: Una somma multistadio basata sull'eseguibilità del codice, la fattibilità della soluzione, la prossimità all'obiettivo della ground-truth (entro un errore relativo del 10%) e la correttezza esatta.
   • Ottimizzazione: Viene utilizzato il Group Relative Policy Optimization (GRPO) per aggiornare la policy, bilanciando la massimizzazione della ricompensa con la regolarizzazione della divergenza KL rispetto al riferimento SFT.

Contributi Chiave

1. Framework di Co-evoluzione a Ciclo Chiuso: A differenza dei metodi precedenti che separano la sintesi dei dati dall'ottimizzazione del modello, EvoOptiGraph li collega tramite l'analisi delle debolezze a livello di grafo, permettendo alla distribuzione di addestramento di adattarsi dinamicamente alle modalità di fallimento in evoluzione del modello.
2. Generatore Basato su Grafi Controllabile: Il framework esegue crossover e mutazioni direttamente su grafi bipartiti attribuiti, consentendo l'evoluzione a livello strutturale oltre le semplici perturbazioni dei parametri. Ciò supporta l'esplorazione sistematica di diverse strutture di ottimizzazione.
3. Adattamento Guidato dalle Debolezze con Feedback Verificabile: Il sistema diagnostica pattern di errore strutturali utilizzando le caratteristiche del grafo ed evolve nuove istanze mirate specificamente a tali fallimenti, ottimizzando il modello con ricompense verificabili basate sul solver.

Risultati Sperimentali

Il framework è stato valutato su sei benchmark pubblici: NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR e IndustryOR.

• Performance: EvoOptiGraph (utilizzando un backbone da 8B parametri) ha raggiunto una precisione media macro di Pass@1 del 78,1%, superando modelli generalisti più grandi (ad esempio, GPT-4o, DeepSeek-V3), metodi agentici (ad esempio, OptiMUS, Chain-of-Experts) e baselines specializzate sottoposte a fine-tuning (ad esempio, ORLM, LLMOPT).
• Diversità dei Dati: Le istanze generate da EvoOptiGraph hanno mostrato una similarità strutturale del 66,93% rispetto ai tipi di problemi originali, significativamente inferiore (indicando una maggiore diversità) rispetto al 93,04% di similarità raggiunto dal metodo testuale OptMATH.
• Studi di Ablazione: Rimuovere il ciclo di co-evoluzione (SFT-only o RL-only) ha causato cali di performance rispettivamente del 9,6% e del 14,7%, confermando che sia l'iniziale radicamento supervisionato che la generazione adattiva guidata dalle debolezze sono critici.
• Generalizzazione: Il modello ha dimostrato una robusta generalizzazione, in particolare su dataset strutturalmente impegnativi come ComplexOR e MAMO-Complex, suggerendo che l'evoluzione mirata dei dati è più efficace del semplice aumento della scala del modello.

Significato e Rivendicazioni

Il paper sostiene che la co-evoluzione mirata tra dati e modello è una strategia efficace per migliorare i LLM nei compiti di modellazione dell'ottimizzazione. Rappresentando i MILP come grafi e utilizzandoli sia per la generazione dei dati che per la diagnosi dei fallimenti, EvoOptiGraph crea un ciclo di auto-miglioramento che aggiorna continuamente la distribuzione di addestramento per affrontare le specifiche lacune del modello.

Gli autori sottolineano che il loro approccio dimostra che l'evoluzione strutturale dei dati può produrre risultati migliori rispetto al semplice aumento della scala del modello o al ricorso a dataset statici. Il framework colma con successo il divario tra lo spazio delle ipotesi di formulazioni di ottimizzazione valide e le capacità effettive del modello, fornendo una via verso pipeline di addestramento più adattive per il ragionamento formale e la ricerca operativa.

Limitazioni Riconosciute:

• L'attuale framework è limitato ai MILP e alla copertura dei generatori seed disponibili.
• La verifica diventa computazionalmente costosa per istanze più grandi.
• Il vettore di debolezza funge da segnale di prioritizzazione pratica piuttosto che da spiegazione causale degli errori.