Können große Sprachmodelle industrietaugliche Optimierungsalgorithmen schreiben? MIT stellt FrontierOR vor – eine Prüfungsumgebung für KI

In den letzten zwei Jahren haben sich LLMs im Bereich „Natürliche Sprache zu mathematischen Modellen“ und „Natürliche Sprache zu Solver-Code“ rasant weiterentwickelt. Die Modelle können Aufgaben verstehen, MIP-Formeln erstellen und Gurobi oder andere Solver aufrufen – sie scheinen erste Fähigkeiten zur Optimierungsmodellierung entwickelt zu haben. Für echte Probleme im industriellen Maßstab reicht dies jedoch bei weitem nicht aus.

Die eigentliche Herausforderung besteht nicht darin, Einschränkungen nacheinander in mathematische Ausdrücke zu übersetzen, sondern Algorithmen zu entwerfen, die auf großen Instanzen lauffähig, präzise und schnell sind. Selbst wenn ein MIP-Modell vollständig korrekt ist, kann es nach der Übergabe an einen universellen Solver innerhalb einer Stunde keine nachweisbaren hochwertigen Lösungen liefern. Aus diesem Grund müssen Operations Research (OR)-Ingenieure in der Praxis immer noch Zerlegungsalgorithmen, Spaltengenerierung, Benders-Zerlegung, lokale Suche, Metaheuristiken und hybride Verfahren aus mathematischer Programmierung und Heuristiken schreiben.

Kürzlich haben Forscher des MIT und anderer Institutionen FrontierOR vorgestellt: einen LLM-Benchmark zur Bewertung der Fähigkeit, Optimierungsalgorithmen im großen Maßstab zu entwerfen.

Im Gegensatz zu herkömmlichen Benchmarks, die nur prüfen, ob ein Modell „modellieren“ oder „einen Solver aufrufen“ kann, konzentriert sich FrontierOR darauf, ob LLMs wie echte OR-Forscher und -Ingenieure handeln können – indem sie skalierbare, hochwertige und effiziente Algorithmen für komplexe Problemstrukturen entwerfen.

Link zum Papier: arxiv.org/abs/2605.25246

Projektseite: frontieror.vercel.app

Link zum Code: github.com/Minw913/FrontierOR

Link zum Datensatz: SmartOR/FrontierOR

Das Kernproblem von FrontierOR lautet: Können die heute stärksten großen Modelle ausgehend von realen Problemen selbstständig wettbewerbsfähige, effiziente Algorithmen entwerfen? Können sie nicht mehr nur „Solver aufrufen“, sondern wie OR-Experten Zerlegungs-, Heuristik-, Such- und hybride Strategien basierend auf der Problemstruktur auswählen?

Die Bedeutung dieser Arbeit liegt darin, dass sie den Schwerpunkt der Bewertung von „LLM für OR“ von der Fähigkeit, Modelle zu schreiben, auf die Fähigkeit verschiebt, Algorithmen zu entwerfen. Dies ist auch eine Hürde, die große Modelle überwinden müssen, um zu echten industriellen Entscheidungssystemen zu gelangen.

Forschungshintergrund

Zahlreiche Benchmarks konzentrieren sich bereits auf die Modellierungsfähigkeit von LLMs bei Optimierungsproblemen – beispielsweise indem Modelle mathematische Programme aus Aufgaben in natürlicher Sprache generieren, Solver aufrufen oder Lösungen auf kleinen Instanzen validieren. Diese Aufgaben sind wichtig, beantworten aber oft keine Frage, die näher an der industriellen Implementierung liegt: Können Modelle auf großen Instanzen, bei denen die Solver-Leistung bereits gesättigt ist, aktiv effizientere Algorithmuspfade entwickeln?

In der Praxis der Operations Research sind universelle Solver nur ein Ausgangspunkt, nicht das Ende. Reale Probleme weisen oft spezielle Strukturen auf: Netzwerkflussstrukturen, zeitliche Zerlegungsstrukturen, Routenstrukturen für Fahrzeuge, Kopplungen von Bestand und Routen, Kopplungen von Maschinen und Arbeitsabläufen bei der Planung sowie Kopplungen von Kapazität und Abdeckung bei der Standortwahl. Gute Algorithmen-Ingenieure nutzen diese Strukturen, um das ursprüngliche Problem zu zerlegen, zu approximieren, zu relaxieren und neu zu kombinieren – und lösen es dann mit einer Mischung aus heuristischen oder exakten Verfahren.

Daher muss ein echter LLM-Benchmark für OR drei Bedingungen erfüllen: ausreichend realistische Aufgabenquellen, ausreichend große Instanzen und eine strenge Bewertung. FrontierOR wurde in diesem Kontext entwickelt: Es stellt keine „Übungsaufgaben zur Optimierung“ für große Modelle auf, sondern wandelt komplexe, in den letzten 30 Jahren in OR-Publikationen begutachtete Probleme in automatisch bewertbare Aufgaben zur Algorithmenentwicklung um.

Tabelle 1: Mehrdimensionale Vergleich von FrontierOR mit repräsentativen Benchmarks für OR und LLM-basierte Optimierung

Forschungsmethodik

Der Erstellungsprozess von FrontierOR lässt sich in vier Schritte zusammenfassen: Auswahl von Aufgaben aus der Literatur, Umwandlung von Papierproblemen in standardisierte Aufgabenkomponenten, automatische und expertenbasierte Qualitätskontrolle sowie Auswahl einer anspruchsvolleren „Hard“-Teilmenge.

• Schritt 1: Auswahl realer Literaturaufgaben. Die Datenquellen umfassen 20+ OR-Zeitschriften aus den Jahren 1992–2025 mit insgesamt 180 Papieren. Ausgewählte Aufgaben erfordern eine klare Problemdefinition, und die ursprüngliche Literatur zeigt bereits den praktischen Wert spezialisierter Algorithmen im Vergleich zu universellen Solvern.
• Schritt 2: Standardisierung der Aufgabenkomponenten. Jedes Papier wird in eine Beschreibung der Aufgabe in natürlicher Sprache, ein mathematisches Modell, eine Gurobi-Referenzimplementierung, eine Referenzlösung und einen unabhängigen Machbarkeitsprüfer umgewandelt.
• Schritt 3: Zweistufige Qualitätsüberprüfung. Zuerst wird durch automatische Kreuzvalidierung geprüft, ob die Gurobi-Referenzlösung mit dem Machbarkeitsprüfer übereinstimmt. Anschließend führen 15 OR-Experten mehrere Überprüfungsrunden durch, um die Konsistenz von Modell, Beschreibung, Code und Prüfer zu gewährleisten.
• Schritt 4: Auswahl der „Hard“-Teilmenge. Aus 180 Aufgaben werden 50 schwierigere ausgewählt – mit Fokus auf Szenarien mit kombinatorischer Explosion, größerem Umfang, stärker gekoppelten Einschränkungen und Fällen, in denen Gurobi innerhalb einer Stunde das Optimum nicht nachweisen kann.

Abbildung 1: Überblick über den FrontierOR-Benchmark – Problemkategorien, Anwendungsbereiche, Instanzengrößen und Erstellungsprozess

Bewertungsprotokoll

Der Bewertungsprozess legt ebenfalls Wert auf End-to-End-Fähigkeiten. Das Modell generiert zuerst ein vollständiges Algorithmusprogramm basierend auf der Aufgabe in natürlicher Sprache. Das Programm durchläuft eine Vorprüfung auf Ausführbarkeit, Machbarkeit und Lösungsqualität auf kleinen Instanzen: Bei Zeitüberschreitung, Unmachbarkeit oder einem Gap von mehr als 10 % im Vergleich zur Gurobi-Lösung auf kleinen Instanzen wird die Bewertung auf großen Instanzen übersprungen.

Nach bestandener Vorprüfung wird das Programm auf mehreren großen Instanzen jeder Aufgabe ausgeführt und mit den von Experten geprüften Gurobi-Referenzlösungen verglichen. FrontierOR verwendet vier Metriken: Execution Rate (Ausführbarkeit), Feasibility (Machbarkeit), Solution Quality (Lösungsqualität) und Quality-Time Efficiency (QTE – umfassende Qualitätseffizienz). QTE ist die strengste Metrik: Nur wenn der relative Abstand des Zielfunktionswerts zur Gurobi-Referenzlösung höchstens 1 % beträgt oder die Gurobi-Lösung übertrifft, gilt der Versuch als erfolgreich.

Abbildung 2: Zweistufiger Bewertungsprozess von FrontierOR – Vorprüfung auf kleinen Instanzen, Bewertung von Qualität und Geschwindigkeit auf großen Instanzen

Experimentelle Ergebnisse

One-Shot: Ausführbarkeit nahe der Obergrenze

Im One-Shot-Szenario muss das Modell ein vollständiges Algorithmusprogramm von Grund auf generieren – es kann eine begrenzte Selbstkorrektur basierend auf Ausführungsfehlern durchführen, darf aber den Algorithmus nicht wiederholt basierend auf Bewertungsfeedback umschreiben. Dieses Szenario prüft die Gesamtfähigkeit des Modells, Aufgaben zu verstehen, zu modellieren, Algorithmen zu entwerfen und zu programmieren.

Die Ergebnisse zeigen, dass die Ausführbarkeit der stärksten Modelle bereits sehr hoch ist. Beispielsweise erreicht GPT-5.3-Codex eine Execution Rate von 0,98 auf der vollständigen „Full“-Menge; Gemini 3.1 Pro und Claude Opus 4.6 erreichen ebenfalls 0,93. Dies zeigt, dass „ob der Code läuft“ für moderne Spitzenmodelle nicht mehr das Haupthindernis darstellt.

Ausführbar bedeutet aber nicht lösbar. Feasibility, Solution Quality und QTE liegen deutlich unter der Execution Rate. Mit anderen Worten: Große Modelle können formal vollständige Optimierungsprogramme schreiben – aber es bleibt schwierig, diese Programme auf industriellem Maßstab machbar, nahezu optimal und schneller als Gurobi zu halten.

Auf einer allgemeinen Ebene übertreffen Spitzenmodelle andere gängige Modelle sowohl auf der vollständigen „Full“-Menge als auch auf der „Hard“-Teilmenge deutlich. Auf der gesamten FrontierOR-Menge liegt die Feasibility der Spitzenmodelle bei 0,60–0,62, während andere gängige Modelle etwa 0,18–0,42 erreichen. Auf der „Hard“-Teilmenge bleibt der Abstand bestehen: Die Spitzenmodelle erreichen 0,49–0,64, während andere gängige Modelle auf 0,13–0,37 abfallen.

Die „Hard“-Teilmenge macht die Unterschiede in der Algorithmenfähigkeit zwischen den Spitzenmodellen noch deutlicher. Auf der gesamten Menge liegen die QTE-Werte der drei Spitzenmodelle in einem engen Bereich von 0,25–0,31 – sie scheinen nahe beieinander zu liegen. Auf der „Hard“-Teilmenge erreicht Claude Opus 4.6 jedoch noch eine QTE von 0,32, während GPT-5.3-Codex auf 0,18 abfällt – ein Unterschied von fast dem Doppelten. Die „Hard“-Teilmenge wird damit zu einem echten „Wasserscheidepunkt für Algorithmen-Ingenieurfähigkeiten“.

Tabelle 2: Ergebnisse der One-Shot-Bewertung von FrontierOR – Execution Rate, Feasibility, Solution Quality und QTE auf der „Full“-Menge und der „Hard“-Teilmenge

Divergenz bei der Algorithmenauswahl

Das Forschungsteam hat die von den Modellen generierten Programme weiter analysiert und ihre Lösungsverfahren in fünf Kategorien unterteilt: reine Solver-Aufrufe, Zerlegungsverfahren, konstruktive Heuristiken, lokale Suche/Metaheuristiken sowie hybride Verfahren aus mathematischer Programmierung und Heuristiken. Diese Analyse ist entscheidend, da sie direkt zeigt, ob das Modell wirklich ein Bewusstsein für Algorithmenentwicklung hat.

Die Ergebnisse zeigen, dass schwächere Modelle stark von reinen Solver-Aufrufen abhängen. Beispielsweise bestehen etwa 99 % der Programme von LLaMA-4-Maverick aus monolithischen Solver-Aufrufen – im Wesentlichen wird das Problem an einen universellen Solver übergeben. Im Gegensatz dazu weist Claude Opus 4.6 die ausgewogenste Verteilung der Verfahren auf: Etwa 37 % sind reine Solver-Aufrufe, 27 % lokale Suche/Metaheuristiken und 27 % hybride Verfahren aus mathematischer Programmierung und Heuristiken.

Noch wichtiger ist, dass nicht reine Solver-Verfahren insgesamt Vorteile bei der QTE-Metrik haben. Dies bedeutet, dass „Verfahrensvielfalt“ selbst ein Wettbewerbsvorteil ist: Je besser das Modell Zerlegungs-, Heuristik- und hybride Algorithmen basierend auf der Problemstruktur auswählen kann, desto wahrscheinlicher erreicht es auf großen Instanzen gleichzeitig hohe Qualität und Geschwindigkeit.

Abbildung 3: Verteilung der Lösungsverfahren in den von verschiedenen Modellen generierten Programmen und Analyse der Fehlermuster

Verschiebung der Fehlermuster: Von „Modellierung falsch“ zu „Suche nicht tief genug“

Die Analyse der Fehlermuster zeigt, dass sich mit steigender Modellfähigkeit die Stellen, an denen Fehler auftreten, systematisch nach hinten verschieben. Schwächere Modelle machen Fehler hauptsächlich in frühen Phasen wie dem Entwurf mathematischer Modelle, der Definition von Einschränkungen oder der Ein-/Ausgabe-Struktur. Stärkere Modelle weisen deutlich weniger Fehler in diesen grundlegenden Bereichen auf – neue Engpässe entstehen bei der Tiefe und Qualität der heuristischen Suche.

Dies ähnelt stark dem Entwicklungspfad menschlicher Algorithmen-Ingenieure. Anfänger machen zuerst Modellierungsfehler: unklare Variablendefinitionen, fehlende Einschränkungen oder nicht übereinstimmende Ein- und Ausgaben. Er