Technische Samenvatting: OPT-Engine: Benchmarken van de Grenzen van LLM's in Optimalisatiemodelvorming via Complexiteitsschaling

1. Probleemstelling

Hoewel Large Language Models (LLM's) veelbelovende vaardigheden hebben getoond in het interpreteren van natuurlijke taal en het genereren van wiskundige modellen voor optimalisatie, blijft hun toepassing op real-world Operations Research (OR) breekbaar. Bestaande benchmarks vertrouwen vaak op statische, vastomlijnde instanties of tekstboekachtige problemen die de combinatorische complexiteit en structurele dichtheid van industriële toepassingen niet vastleggen. Bovendien bestaat er een aanzienlijke prestatiekloof tussen het succes van LLM's in competitieve wiskunde en hun vermogen om complexe optimalisatieproblemen te formuleren en op te lossen, met name naarmate de probleemomvang toeneemt. De gemeenschap mist een rigoureus, uitbreidbaar kader om systematisch de grenzen van geautomatiseerde probleemformulering te onderzoeken en om onderscheid te maken tussen de effectiviteit van verschillende redeneringsparadigma's (Pure-tekstredenering versus Oplosser-geïntegreerde redenering) onder gecontroleerde complexiteitsschaling.

2. Methodologie: Het OPT-Engine Kader

Om deze hiaten aan te pakken, introduceren de auteurs OPT-Engine, een uitbreidbaar benchmarkkader dat is ontworpen om probleeminstanties te genereren met kwantificeerbare en controleerbare complexiteit.

2.1. Benchmarktaxonomie

OPT-Engine omvat tien canonieke OR-probleemklassen, verdeeld over twee niveaus:

• Lineaire Programmering (LP): Voorraadbeheer, portefeuilletoewijzing, productie, transport en vervuilingscontroleproblemen.
• Gemengd-geheeltallige Programmering (MIP): Reisende-verkoopsterprobleem (TSP), Rugzakprobleem, Bin Packing, Job-Shop Planning en Stroomnetwerk met minimale kosten.

2.2. Schaalbaar Generatieproces

Het kader hanteert een viertrapsproces om verifieerbare probleeminstanties te genereren:

1. Numerieke Instantiegeneratie: Een generator $G$ koppelt een probleemklasse en een vector voor complexiteitscontrole $\theta$ (bijvoorbeeld het aantal steden $N_{steden}$ voor TSP) aan een numerieke instantie. Cruciaal is dat deze fase een oplossertemplate gebruikt om de grondwaarheid (ground-truth) optimale oplossing en doelwaarde te berekenen.
2. Canonieke Probleemconstructie: De numerieke instantie wordt via een gestructureerde template omgezet in een formele, canonieke probleemstelling $s_c$.
3. Probleemaugmentatie: Een toegewijde LLM-agent herschrijft de canonieke uitspraak in diverse, contextrijke natuurlijke taalverhalen ($s_r$) om real-world scenario's te simuleren, terwijl de onderliggende wiskundige structuur behouden blijft.
4. Instantievalidatie: Een validatiemodule, die een LLM als rechter combineert met regelgebaseerde verifiers, waarborgt dat de herschreven verhalen structurele equivalentie en numerieke consistentie met de grondwaarheid behouden.

2.3. Evaluatieparadigma's

Het kader evalueert twee primaire redeneringsbenaderingen:

• Pure-tekstredenering (PTR): De LLM gebruikt Chain-of-Thought (CoT) om de oplossing end-to-end af te leiden zonder externe hulpmiddelen.
• Oplosser-geïntegreerde redenering (SIR): De LLM vertaalt het probleem naar uitvoerbare code (bijvoorbeeld Gurobi/COPT) die vervolgens wordt opgelost door een externe deterministische oplosser.
• Computational PTR (CompPTR): Een tussenvorm waarbij de LLM Python-primitieven gebruikt voor lokale berekeningen, maar wordt beperkt tot het aanroepen van globale optimalisatieoplossers.

3. Belangrijkste Resultaten

3.1. Schaling en Robuustheid

• Superioriteit van SIR: Naarmate de probleemcomplexiteit toeneemt (grotere dimensies en beperkingen), behoudt SIR een hoge nauwkeurigheid of vertoont slechts een lichte achteruitgang. Daarentegen lijdt PTR onder een kritiek robuustheidshiaat, waarbij de prestaties aanzienlijk instorten naarmate de probleemgrootte toeneemt.
• Effecten van Modelgrootte: Hoewel kleinere modellen (bijvoorbeeld Qwen3-4B) SIR bij lage complexiteit kunnen overtreffen vanwege fouten in codegeneratie binnen SIR, is dit voordeel tijdelijk. Met Reinforcement Learning from Verifiable Rewards (RLVR) om codegeneratie te verbeteren, presteert SIR consistent beter dan PTR over alle dimensies.

3.2. Mechanistische Foutmodi

• Rekenen versus Structuur: Foutendecompositie toont aan dat PTR-fouten tweeledig zijn: naarmate de complexiteit groeit, falen modellen eerst in het voldoen aan globale logische beperkingen (instorting van haalbaarheid) en vervolgens in het behalen van numerieke precisie.
• Beperkingen van Rekenhulpmiddelen: Hoewel CompPTR (het toevoegen van Python-tools aan PTR) rekenfouten mitigeert en lokale haalbaarheid verbetert, faalt het in het afdwingen van globale optimalisatiebeperkingen. Het model kan geen holistische combinatorische afhankelijkheden internaliseren, wat leidt tot prestatiedegradatie vergelijkbaar met standaard PTR bij hoge schalen.

3.3. Diagnose van Knelpunten

De auteurs hebben diagnostische experimenten uitgevoerd om de primaire bronnen van fouten te isoleren:

• Taalkundige Complexiteit: Variëren van de perplexiteit (PPL) van probleembeschrijvingen had een verwaarloosbaar effect op de nauwkeurigheid.
• Objective Perturbaties: Het toevoegen van constante verschuivingen aan doelwitten degradeerde de prestaties niet significant.
• Beperkingaugmentatie: De introductie van aanvullende, wiskundig rechttoe rechtaarde beperkingen (bijvoorbeeld "precies één van twee wegen moet worden opgenomen") veroorzaakte een aanzienlijke en consistente daling van de nauwkeurigheid over alle probleemklassen en paradigma's.

Conclusie over Knelpunten: Het primaire knelpunt voor huidige SOTA LLM's in optimalisatie is niet taalkundig begrip of formulering van doelwitten, maar de geautomatiseerde formulering van beperkingen. Modellen worstelen om te generaliseren buiten canonieke, tekstboekachtige formuleringen om de rijke, beperkingsrijke variaties aan te pakken die in real-world toepassingen voorkomen.

4. Bijdragen

1. OPT-Engine Kader: Een uitgebreid, uitbreidbaar benchmarkkader dat fijnmazige, schaalbare controle mogelijk maakt over wiskundige structuur en taal voor het evalueren van LLM's in optimalisatiemodelvorming.
2. Paradigma-evaluatie: Empirisch bewijs dat aantoont dat PTR geen robuustheid bezit bij schaling, terwijl SIR essentieel is voor het behoud van nauwkeurigheid in scenario's met hoge complexiteit.
3. Analyse van Tool-integratie: Bevindingen dat externe rekenhulpmiddelen weliswaar lokale berekeningen ondersteunen, maar de fundamentele onbekwaamheid van LLM's om zonder oplosser-integratie te voldoen aan globale optimalisatiebeperkingen niet oplossen.
4. Identificatie van Knelpunten: Het aanwijzen van beperkingsformulering als het kritieke faalpunt, en het onderscheiden daarvan van probleembegrip of perturbaties van doelwitten.

5. Betekenis en Aanspraken

Het artikel stelt dat OPT-Engine een noodzakelijke diagnostische rigoreusheid biedt om het vakgebied voorbij geïsoleerde demonstraties en zij-aan-zij vergelijkingen op statische datasets te brengen. Door een protocol voor complexiteitsschaling vast te stellen, onthult het kader dat huidige LLM's zwaar vertrouwen op patronen uit canonieke trainingsdata en niet robuust kunnen redeneren over nieuwe combinaties van beperkingen.

De auteurs stellen dat deze bevindingen de beperkingen van huidige paradigma's verduidelijken en een gestructureerde routekaart bieden voor het ontwikkelen van LLM's van de volgende generatie. Zij benadrukken dat optimalisatiemodelvorming alleen levensvatbaar is in industriële omgevingen als modellen voorbij "redeneringsillusies" gaan en betrouwbaarheid bereiken in beperkingsformulering. Het artikel concludeert met de erkenning dat, hoewel de focus ligt op exacte oplossingen (LP/MIP), toekomstig werk heuristieken voor NP-moeilijke problemen moet verkennen en het kader moet uitbreiden naar niet-lineaire en stochastische domeinen. De code en data zijn vrijgegeven om dit toekomstige onderzoek te faciliteren.