Stephan Jansen, Java-Champion und Devoxx Gründer, Habe an chatgpt herumgebastelt um „den perfekten Konferenzplan zu erstellen“. Es gelang ihm, für einen Tag brauchbare Ergebnisse zu erzielen, für die gesamte fünftägige Konferenz jedoch nicht. Geoffrey de Smet, CTO und Gründer von Zeitfalte (ehemals OptaPlanner) argumentierte, dass der KI-Assistent scheitert, weil er weiche Einschränkungen nicht so effektiv behandeln kann wie eine spezialisierte Planungsbibliothek.
Das Problem ist recht komplex: Jeder der 210 Vorträge kann jedem der 40 Zeitfenster und 10 Räume zugeordnet werden. Das sind 400 Möglichkeiten pro Vortrag. Das ergibt 10279 Fahrplankombinationen. de Smet reagierte mit den Worten: „Der ideale Zeitplan ist schwerer zu finden als die Nadel im Heuhaufen.“
Weil es ein ist NP-hart Problem, es gibt kein Allheilmittel. Selbst Algorithmen, die den Suchraum um 99 % reduzieren, müssen immer noch 10 durchsuchen279 Kombinationen. „Das ist unmöglich“, sagte de Smet, „selbst in einer Milliarde Jahren wird die gesamte Computerleistung auf diesem Planeten verschwinden.“
InfoQ wandte sich an Jansen und de Smet, um mehr über ihre Erfahrungen zu erfahren und ob Große Sprachmodelle kann einen sofort einsatzbereiten optimalen Zeitplan für eine fünftägige Veranstaltung bereitstellen.
InfoQ: Warum ist das Planungsproblem so schwer zu lösen?
Jansen: Bei der Planung von 210 Vorschlägen über fünf Tage hinweg besteht der erste Schritt darin, die Verfügbarkeit der Redner zu berücksichtigen, um sicherzustellen, dass es keine Konflikte gibt. Um ein abwechslungsreiches Erlebnis zu bieten, ist es wichtig, die gleichzeitige Planung ähnlicher Themen zu vermeiden. Idealerweise sollten Sie die Sitzungen so gestalten, dass Sie mit Einführungsvorträgen beginnen und dann zu fortgeschritteneren Vorträgen über die vorherigen Themen übergehen. Sie möchten auch die beliebtesten Vorträge in den größeren Räumen planen.
InfoQ: Kann ChatGPT eine geeignete Lösung bieten?
Jansen: Bitten Sie ChatGPT in einer einmaligen Eingabeaufforderung um die Generierung Ein bestmöglicher Zeitplan ist derzeit nicht möglich. Es ist jedoch eine andere Sache, es zu bitten, Code für die Planung zu generieren. Dadurch gelang es, einen Zeitplan für einen Konferenztag zu erstellen.
de Smet: Stephans Gen AI-Ansatz generiert ein Modell für einen Produktionslöser und findet eine praktikable Lösung für eine eintägige Konferenz. Es ist ein vielversprechender Ansatz: Wir haben ähnliche Experimente durchgeführt, um neue Planungsmodelle für Timefold zu entwickeln. Derzeit lassen sich diese generierten Modelle nicht skalieren und funktionieren noch nicht richtig, insbesondere bei weichen Einschränkungen. Stephan und ich haben eine Wette abgeschlossen, um zu sehen, ob der GenAI-Ansatz a schlagen könnte handgeschriebenes Modell. Bis jetzt, Letzterer gewinnt deutlich. Aber es bedarf noch weiterer Forschung: Stephan öffnete mir die Augen, dass LLM-generierte Timefold-Modelle tatsächlich funktionieren könnten.
InfoQ: Wie geht Timefold mit diesem Problem um?
de Smet: Timefold akzeptiert Einschränkungen als Code. Andere Produktionslöser erwarten mathematische Gleichungen als Eingabe, auch wenn diese im Code geschrieben sind. Um beispielsweise die Einschränkung zu implementieren, dass ein Redner zwischen zwei Vorträgen eine Pause von mindestens 30 Minuten einlegen muss, verwendet ein Timefold-Modell funktionale Programmierung für die Talk- und Speaker-Klassen und keinen Code, der x + y
InfoQ: Was sind die Hardwareanforderungen von Timefold?
de Smet: Timefold ist CPU-gebunden. Während der Lösung gibt es keine E/A und in den meisten Fällen werden weniger als 2 GB Speicher verwendet. Es gibt keine Trainingsphase. In der Produktion wird es normalerweise mit 4 CPUs für 30 Minuten pro Datensatz ausgeführt.
Große Unternehmen führen jede Nacht über einen Zeitraum von fünf Stunden 100 Datensätze aus, die 40 CPUs beanspruchen.
InfoQ: Welche Open-Source-Optionen gibt es derzeit?
Jansen: Es gibt mehrere von google implementierte OSS-Bibliotheken (OR-Tools) oder Microsoft (Z3-Prover). Meist in Python oder C++ verfügbar. Wir hatten auch einige Präsentationen von anderen Lösungen auf der Devoxx.
de Smet: Da fallen mir ein paar Bibliotheken ein, die in den Programmiersprachen geschrieben sind, die Timefold unterstützt (Java und Kotlin) oder bald unterstützen möchte (wie Python).
In Java gibt es einige davon Schokoladenlöser, JaCoP, JOpt. Außerdem sind einige Optionen in Kotlin implementiert: Konopt, KOpt und sogar eine Kotlin-Implementierung von OptaPlanner: KIE.
In Python sind auch gute Löser geschrieben, z CPLEX oder MÜNZE-ODER.
Auch wenn LLMs Entwicklern dabei helfen können, eine einfachere Lösung zu finden, indem sie das Modell teilweise generieren, ist es derzeit nicht möglich, auf die Frage zu antworten: „Wie kann ich die Vorträge für eine Konferenz planen?“ Erfahrung und der Einsatz von Tools wie KI-Assistenten führen also sowohl aus Ergebnis- als auch aus Ressourcensicht zur effizientesten Lösung.
