Technische Samenvatting: EvoOptiGraph

Probleemstelling

Het automatiseren van de vertaling van natuurlijke taal beslissingsproblemen naar formele wiskundige optimalisatiemodellen (specifiek Mixed-Integer Linear Programs, of MILP's) blijft een significante uitdaging voor Large Language Models (LLM's). Huidige benaderingen kampen met twee primaire beperkingen:

1. Gebrek aan structurele diversiteit in trainingsdata: Bestaande benchmarks (bijv. NL4Opt, MAMO) dekken slechts een smalle subset van geldige optimalisatieformuleringen. Datasynthese-pipelines vertrouwen vaak op vaste templates met parametervariaties, wat faalt in het genereren van de brede structurele diversiteit die vereist is voor robuuste generalisatie.
2. Statische trainingspipelines: De meeste trainingsopstellingen gebruiken een bevroren dataset die vooraf aan de modeltraining is geconstrueerd. Deze ontkoppeling voorkomt dat het systeem specifieke structurele regimes kan identificeren waar het model faalt en nieuwe instanties kan genereren om die zwaktes gericht aan te pakken.

Methodologie: EvoOptiGraph

De auteurs stellen EvoOptiGraph voor, een zwakte-gestuurd co-evolutieframework dat datageneratie en modeltraining koppelt via een expliciete structurele representatie. Het framework werkt in een gesloten lus bestaande uit drie kerncomponenten:

1. Graafgebaseerde structurele representatie

Elke MILP wordt gerepresenteerd als een geattributeerde bipartiete graaf $G = (V, E, A)$:

• Knopen: Eén knoop per beslissingsvariabele ($V_{var}$) en één per beperking plus een speciale objectieveven ($V_{con}$).
• Randen: Verbinden variabelen met beperkingen/objectieven waar coëfficiënten niet nul zijn; randgewichten slaan de coëfficiëntwaarden op.
• Attributen: Knopen slaan metadata op zoals variabelenbounds, types (integer/continu/binair), beperkingsvormen (senses) en right-hand-side waarden.
  Deze representatie maakt deterministische compilatie naar solver-code (bijv. Gurobi mogelijk en ondersteunt validiteitsbehoudende genetische operaties.

2. Controleerbare datageneratie via graaf-evolutie

In plaats van tekst of parameters te veranderen, evolueert EvoOptiGraph optimalisatie-instanties direct in de graafruimte met behulp van genetische operatoren:

• Crossover: Wisselt compatibele subgrafen uit tussen ouder-instanties (bijv. het combineren van een productieplanning-beperking met een knapzakprobleem-beperking). Cross-class crossover is toegestaan om de structurele diversiteit te vergroten.
• Mutatie: Werkt op drie niveaus:
  • Parameter: Verandert coëfficiënten, bounds en RHS-waarden.
  • Structureel: Voegt variabelen/beperkingen toe, verwijdert ze of wijzigt ze, terwijl lineariteit behouden blijft.
  • Schaal: Verandert de omvang van het probleem (bijv. het uitbreiden van supply/demand nodes).
• Fitnessfunctie: Kandidaten worden gescoord op basis van:
  • Moeilijkheidsgraad: Afgeleid van solver-statistieken (oplostijd, branch-and-bound nodes).
  • Diversiteit: Gemeten via Graph Edit Distance (GED) ten opzichte van de huidige populatie.
  • Afstemming op zwaktes: Cosinus-gelijkenis tussen de structurele kenmerken van de instantie en de huidige zwaktevector van het model.

3. Tweefasig modeltraining en co-evolutie-lus

Het trainingsproces wisselt af tussen model-fitting en data-evolutie:

1. Opwarming (SFT): Het basis-LLM wordt supervised fine-tuned op een initiële populatie van geverifieerde instanties gegenereerd uit expert seed-generators.
2. Zwakteanalyse: Het huidige model wordt geëvalueerd op een helder gehouden validatieset. Een XGBoost-classifier voorspelt falen op basis van graaf-afgeleide structurele kenmerken. SHAP-waarden worden berekend op foutgevallen om een zwaktevector ($w$) te genereren die de structurele eigenschappen benadrukt die het meest geassocieerd zijn met model-fouten.
3. Zwakte-gestuurde RL (RLVR): De evolutionaire generator wordt gestuurd richting instanties waarvan de structurele kenmerken overeenkomen met de zwaktevector ($\tilde{f}_{weak}$). Het model wordt vervolgens bijgewerkt met behulp van Reinforcement Learning with Verifiable Rewards (RLVR).
   • Beloningen: Een meerfasige som gebaseerd op code-uitvoerbaarheid, oplossing-haalbaarheid, nabijheid tot de grondwaarheid-objectieve (binnen 10% relatieve fout), en exacte correctheid.
   • Optimalisatie: Group Relative Policy Optimization (GRPO) wordt gebruikt om het beleid bij te werken, waarbij een balans wordt gezocht tussen beloningsmaximalisatie en KL-divergentie regularisatie tegenover de SFT-referentie.

Belangrijkste Bijdragen

1. Closed-Loop Co-evolutieframework: In tegen tegenstelling tot eerdere methoden die datasynthese en modeloptimalisatie scheiden, koppelt EvoOptiGraph deze via graaf-niveau zwakteanalyse, waardoor de trainingsdistributie dynamisch kan worden aangepast aan de evoluerende foutmodi van het model.
2. Controleerbare Graafgebaseerde Generator: Het framework voert crossover en mutatie direct uit op geattributeerde bipartiete grafen, wat structurele evolutie op niveau mogelijk maakt die verder gaat dan eenvoudige parametervariaties. Dit ondersteunt systematische exploratie van diverse optimalisatiestructuren.
3. Zwakte-gestuurde Adaptatie met Verifieerbare Feedback: Het systeem diagnosticeert structurele foutpatronen met behulp van graafkenmerken en evolueert nieuwe instanties die specifiek gericht zijn op die fouten, waarbij het model wordt geoptimaliseerd met verifieerbare solver-gebaseerde beloningen.

Experimentele Resultaten

Het framework werd geëvalueerd op zes publieke benchmarks: NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR en IndustryOR.

• Prestaties: EvoOptiGraph (met een 8B parameter backbone) behaalde een macro-gemiddelde Pass@1 nauwkeurigheid van 78,1%, waarmee het grotere generalistische modellen (bijv. GPT-4o, DeepSeek-V3), agentische methoden (bijv. OptiMUS, Chain-of-Experts) en gespecialiseerde fine-tuned baselines (bijv. ORLM, LLMOPT) overtrof.
• Datadiversiteit: Instanties gegenereerd door EvoOptiGraph vertoonden een structurele gelijkenis van 66,93% met de originele probleemtypen, wat aanzienlijk lager is (wat duidt op hogere diversiteit) dan de 93,04% gelijkenis bereikt door de tekstgebaseerde OptMATH methode.
• Ablatie-studies: Het verwijderen van de co-evolutie-lus (SFT-alleen of RL-alleen) resulteerde in prestatieverliezen van respectievelijk 9,6% en 14,7%, wat bevestigt dat zowel de initiële supervised grounding als de adaptieve zwakte-gestuurde generatie cruciaal zijn.
• Generalisatie: Het model demonstreerde robuuste generalisatie, met name op structureel uitdagende datasets zoals ComplexOR en MAMO-Complex, wat suggereert dat gerichte data-evolutie effectiever is dan simpelweg de modelgrootte schalen.

Betekenis en Claims

Het artikel claimt dat gerichte data-model co-evolutie een effectieve strategie is voor het verbeteren van LLM's bij optimalisatiemodelleringstaken. Door MILP's als grafen te representeren en deze te gebruiken voor zowel datageneratie als foutdiagnose, creëert EvoOptiGraph een zelfverbeterende lus die de trainingsdistributie continu bijwerkt om de specifieke blinde vlekken van het model aan te pakken.

De auteurs benadrukken dat hun aanpak aantoont dat structurele data-evolutie betere resultaten kan opleveren dan simpelweg de modelomvang vergroten of vertrouwen op statische datasets. Het framework slaagt erin de kloof te overbruggen tussen de hypotheseruimte van geldige optimalisatieformuleringen en de werkelijke capaciteiten van het model, en biedt hiermee een pad naar meer adaptieve trainingspipelines voor formeel redeneren en operations research.

Erkende Beperkingen:

• Het huidige framework is beperkt tot MILP's en de dekking van de beschikbare seed-generators.
• Verificatie wordt computationeel duur voor grotere instanties.
• De zwaktevector dient als een praktisch prioritiseringssignaal in plaats van een causale verklaring van fouten.