DRAGON: LLM-basierte Agenten lösen große kombinatorische Optimierungsprobleme

In einer bahnbrechenden Veröffentlichung stellt DRAGON – Decomposition and Reconstruction Agents Guided OptimizatioN – ein neues Paradigma vor, das die Leistungsfähigkeit von Large Language Models (LLMs) für komplexe kombinatorische Optimierungsaufgaben (COPs) deutlich erweitert. Während herkömmliche LLM‑Ansätze bei Problemen mit mehr als 30 Knoten an ihre Grenzen stoßen, demonstriert DRAGON, wie LLMs in Kombination mit klassischen Metaheuristiken skalierbare und robuste Lösungen liefern können.

Der Ansatz beginnt mit einer globalen Ausgangslösung und nutzt autonome Agenten, um Regionen mit hohem Optimierungspotenzial zu identifizieren. Diese Bereiche werden dann in handhabbare Teilprobleme zerlegt, die jeweils als kompakte, lokalisierte Aufgaben formuliert werden. Durch gezielte Prompting‑Strategien, unterstützt von einer adaptiven Erfahrungs‑Memory, löst das System jedes Teilproblem mit dem LLM. Anschließend werden die lokal optimierten Ergebnisse systematisch wieder in den ursprünglichen globalen Kontext integriert, wodurch die Gesamtqualität der Lösung kontinuierlich verbessert wird. Die Agenten lernen dabei aus Feedback und verknüpfen symbolisches Denken mit heuristischen Suchmethoden.

Die experimentellen Ergebnisse sind beeindruckend: Im Gegensatz zu bestehenden LLM‑basierten Solver‑Ansätzen, die meist nur kleine Instanzen bewältigen können, erzielt DRAGON konsistent machbare Lösungen für Benchmarks wie TSPLIB, CVRPLIB und Weibull‑5k Bin‑Packing. Besonders bemerkenswert ist die nahezu optimale Performance (nur 0,16 % Gap) bei Knapsack‑Problemen mit über drei Millionen Variablen. Diese Erfolge zeigen, dass DRAGON die Grenzen der LLM‑gestützten Optimierung sprengt und einen neuen Standard für die Lösung großer kombinatorischer Probleme setzt.