EvoCut: Intelligente Evolutionäre Sprachmodelle verbessern Ganzzahlprogramme

Ganzzahlprogramme (Integer Programming) sind das Herzstück vieler wichtiger kombinatorischer Optimierungsaufgaben, bleiben jedoch wegen ihrer NP‑schweren Natur ein großes Problem. Ein bewährter Ansatz zur Beschleunigung dieser Programme ist das manuelle Entwerfen von „Acceleration Cuts“ – speziellen Ungleichungen, die die Leistung von Solver*innen deutlich steigern. Dieser kreative Prozess erfordert jedoch tiefgehendes Fachwissen und ist bislang nicht automatisiert.

Mit dem neuen Rahmenwerk EvoCut wird dieser Schritt revolutioniert. EvoCut kombiniert große Sprachmodelle (LLMs) mit einer evolutionären Suche, um Acceleration Cuts automatisch zu generieren. Zunächst erstellt ein LLM-basierter Initialisierungsagent eine vielfältige Population potenzieller Cuts. Jeder Cut wird anschließend empirisch getestet, indem geprüft wird, ob die optimale Lösung erhalten bleibt und ob er Bruchteil-Lösungen aus dem Lösungsraum ausschließt. Auf Basis dieser Bewertung wird die Population iterativ durch evolutionäre Kreuzung und Mutation verfeinert.

Die Wirksamkeit eines Cuts wird dabei durch die relative Reduktion der Optimalitätslücke des Solvers gemessen. In Vergleich zu herkömmlichen Praktiken reduziert EvoCut die Optimalitätslücke um 17 % bis 57 % innerhalb eines festgelegten Zeitrahmens. Gleichzeitig erzielt es dieselben Lösungen bis zu viermal schneller und liefert innerhalb derselben Zeit bessere Ergebnisse. Dabei benötigt EvoCut keine Eingaben von menschlichen Experten, generiert zuverlässig neue Cuts, verbessert bestehende und verifiziert sie empirisch – und das sogar auf bisher unbekannte Probleminstanzen.

Der komplette Code ist frei verfügbar unter https://github.com/milad1378yz/EvoCut.