Technische Samenvatting: Strategiebewuste Optimalisatiemodeling met Redenerende LLM's (SAGE)

Probleemstelling

In operations research (OR) is de belangrijkste bottleneck in geautomatiseerde workflows vaak niet de uitvoering van solvers, maar de formulering van door de solver uitvoerbare wiskundige programma's uit natuurlijke taalbeschrijvingen. Hoewel Large Language Models (LLM's) bekwaamheid hebben aangetoond in het genereren van syntactisch geldige optimalisatiecode, worstelen ze vaak met het selecteren van effectieve Modelleerstrategieën.

Huidige benaderingen behandelen modeling doorgaans als een directe vertaalttaak, waarbij variabelen en constraints worden gegenereerd zonder een expliciete, hoog-niveau paradigma-selectie (bijvoorbeeld kiezen tussen stromingsgebaseerde, toewijzingsgebaseerde of tijdsgeïndexeerde formuleringen). Dit gebrek aan een expliciete strategie leidt tot:

1. Onjuiste Formuleringen: Modellen kunnen beslissingsvariabelen definiëren over ongeldige indexruimten (bijvoorbeeld het aannemen van zendingen tussen niet-bestaande stadsparen), wat runtime-fouten veroorzaakt.
2. Inefficiënt Oplossen: Zelfs wanneer correct, kunnen verschillende paradigma's voor hetzelfde probleem leiden tot sterk verschillende modelgroottes, constraint-dichtheid en convergentietijden van de solver.
3. Impliciete Redenering: Bestaande datasets en trainingsmethoden laten vaak het strategische redeneerproces weg, waardoor het voor modellen moeilijk is om te leren hoe ze zich moeten committeren aan een globaal ontwerpparadigma voordat ze specifieke constraints instantiëren.

Methodologie: Het SAGE-kader

De auteurs stellen SAGE (Strategy-Aware Guided rEasoning) voor, een tweefasig kader dat is ontworpen om de Modelleerstrategie expliciet te maken tijdens zowel dataconstructie als post-training.

Fase 1: Multi-Strategie Data Synthese

Om de schaarste aan strategie-niveau redeneringsdata aan te pakken, construeren de auteurs een door de solver geverifieerde, multi-strategie dataset:

• Strategiegeneratie: Een teacher LLM genereert $K$ verschillende kandidaat-modelleerstrategieën (paradigma's) voor elk optimalisatieprobleem.
• Redenering en Codegeneratie: Voor elke strategie produceert het model een redeneerspoor (definiërend sets, parameters, variabelen en constraints) en bijbehorende Gurobi Python-code.
• Solververificatie: gegenereerde codes worden uitgevoerd. Outputs die niet draaien, onhaalbaar/onbeperkt zijn terwijl ze haalbaar zouden moeten zijn, of niet overeenkomen met grond-waarheid oplossingen, worden verworpen.
• De-duplicatie: Een LLM-as-Judge filtert semantisch redundante strategieën eruit, waarbij alleen distincte paradigma's worden behouden om diversiteit in het trainingscorpus te waarborgen.

Fase 2: Strategiebewuste Training

Het studentmodel wordt getraind met een combinatie van Supervised Fine-Tuning (SFT) en Reinforcement Learning (RL) met solverfeedback.

1. Gestructureerd Redeneersjabloon: Het model wordt gedwongen een <thought>-blok uit te zenden dat drie geordende segmenten bevat:
   • <strategy>: Identificeert de probleemklasse, selecteert een paradigma en commit tot de kernbeslissingsvariabelen.
   • <modeling>: Instantieert de formulering consistent met de gekozen strategie.
   • <check>: Verifieert globale consistentie (indexdomeinen, lustrumdimensies) en verwijdert redundanties.
2. Segment-gewogen GRPO: De auteurs introduceren een variant van Group Relative Policy Optimization (GRPO) die hogere token-gewichten toekent aan het <strategy>-segment dan aan de <modeling>- of <check>-segmenten. Dit adresseert het credit assignment-probleem in redenering op lange termijn, waarbij ervoor wordt gezorgd dat vroege hoog-niveau beslissingen sterkere optimalisatiesignalen ontvangen.
3. Composiete Beloningsfunctie: Het RL-doel optimaliseert voor drie componenten:
   • Formaatconformiteit: Naleving van de gestructureerde sjabloon-tags.
   • Uitkomstcorrectheid: Gebaseerd op solveruitvoering (haalbaarheid, optimaliteit en overeenstemming met grond-waarheid).
   • Solverefficiëntie: Een beloningsterm die alleen wordt toegepast op correcte oplossingen, en hoge oplostijden, iteratieaantallen of grote optimaliteitsgaten bestraft.

Belangrijkste Bijdragen

1. Constructie van een Multi-Strategie Dataset: Het creëren van een dataset met (vraag, redenering, code) triades waarbij meerdere distincte, door de solver geverifieerde strategieën per probleem worden gegenereerd, waarbij paradigma-selectie expliciet wordt gescheiden van instantiatie.
2. Segment-gewogen GRPO: Een nieuw reinforcement learning-algoritme dat strategie-niveau beslissingen binnen de redeneringstrajectie opwaardeert om credit assignment voor modelleertaken op lange termijn te verbeteren.
3. Efficiëntiebewuste Training: De integratie van solver-efficiëntiemetrieken (oplostijd, iteraties) direct in de beloningsfunctie, waardoor het model niet alleen correcte formuleringen leert, maar ook efficiënte.

Experimentele Resultaten

De auteurs hebben SAGE geëvalueerd op acht benchmarks die synthetische en real-world settings omvatten (bijvoorbeeld NL4OPT, MAMO, ComplexOR, IndustryOR).

• Pass@1-nauwkeurigheid: SAGE verbeterde de gemiddelde Pass@1-nauwkeurigheid van 72,7% (sterkste open-source baseline, SIRL) naar 80,3%. Het presteerde beter dan zowel zero-shot generalist LLM's als andere fine-tuned of RL-gebaseerde baselines, met name bij complexe taken waar de gemiddelde verbetering ongeveer 15,4% bedroeg.
• Modelleerdiversiteit (Pass@K): Met meerdere generaties ontdekte SAGE meer distincte correcte formuleringen. Bij Pass@16 toonde het een 19–29% verbetering in component-niveau diversiteit (distincte variabele ontwerpen, constraint-structuren en doelstellingen) vergeleken met baselines.
• Solverefficiëntie: Bij de grootste probleemomvang produceerde SAGE formuleringen met 14,2% minder constraints dan de baseline. Hoewel het iets meer variabelen gebruikte (een extended formuleringstechniek), waren de resulterende constraint-matrices heter (lagere NNZ), wat leidde tot aanzienlijk snellere oplostijden en minder solver-iteraties.
• Ablatiestudies: Het verwijderen van de reinforcement learning-fase, het gestructureerde sjabloon of de segment-gewichting resulteerde in significante prestatiedalingen, wat bevestigt dat expliciete strategie-redenering en gewogen credit assignment cruciaal zijn voor het hanteren van structureel complexe problemen.

Betekenis en Claims

Het artikel stelt dat het expliciet maken van de Modelleerstrategie een noodzakelijke stap is voor betrouwbare en efficiënte geautomatiseerde optimalisatiemodeling. Door de keuze van het paradigma (bijvoorbeeld stromingsgebaseerd versus toewijzingsgebaseerd) te behandelen als een eerste-klass planningslaag in plaats van een impliciet bijproduct van codegeneratie, overbrugt SAGE de kloof tussen probleemintentie en solver-klaar formuleringen.

De auteurs concluderen dat hun benadering compacte modellen in staat stelt robuuste optimalisatiegedragingen te verwerven, waarbij formuleringen worden geproduceerd die niet alleen wiskundig correct zijn, maar ook computationeel efficiënt. Dit suggereert dat toekomstige vooruitgang in geautomatiseerd OR zich moet richten op expliciete strategie-redenering en solver-informeerde feedbacklussen, in plaats van uitsluitend op het schalen van modelparameters of het verbeteren van codesyntaxis.