Stephan Janssen, Java Champion and Devoxx founder, tinkered with ChatGPT to "create the perfect conference schedule". He managed to obtain feasible results for one day, but not for the whole five-day conference. Geoffrey de Smet, CTO and founder of Timefold (formerly OptaPlanner), argued that the AI Assistant fails by not being able to treat soft constraints as effectively as a specialized planning library.
The problem is a rather complex one: each of the 210 talks can be assigned to any of the 40 time slots and 10 rooms. That’s 400 possibilities per talk. That results in 10277 schedule combinations. De Smet reacted by saying "The ideal schedule is harder to find than a needle in a haystack."
Because it’s an NP-hard problem, there’s no silver bullet. Even algorithms that reduce the search space by 99%, still need to comb through 10279 combinations. "That's impossible," said de Smet, "even in a billion years, with all the computer power on this planet."
InfoQ reached out to Janssen and de Smet to learn about their experience and whether Large Language Models can provide an out-of-the-box optimal schedule for a five-day event.
InfoQ: Why is the scheduling problem such a hard problem to solve?
Stephan Janssen: When scheduling 210 proposals over five days, the first step is to consider the speakers' availability to ensure there are no conflicts. Then, to offer a varied experience, it's crucial to avoid scheduling similar topics at the same time. Ideally, you'll want to arrange the sessions starting with introductory talks and progressing to more advanced ones related to the earlier topics. You also want to schedule the most favorite talks in the bigger rooms.
InfoQ: Can ChatGPT provide a proper solution?
Janssen: Asking ChatGPT in a one-shot prompt to generate the best possible schedule is currently not possible. However, asking it to generate code for scheduling is a different story. That managed to create a schedule for a day of conference.
Geoffrey de Smet: Stephan’s Gen AI approach generates a model for a production solver and finds a feasible solution for a one-day conference. It’s a promising approach: we‘ve done similar experiments to generate new planning models for Timefold. For now, those generated models don’t scale and don’t work correctly yet, especially for soft constraints.
Stephan and I made a bet to see if the GenAI approach could beat a hand-written model. So far, the latter is winning significantly. But more research is needed: Stephan opened my eyes that LLM-generated Timefold models could actually work.
InfoQ: How does Timefold tackle this problem?
De Smet: Timefold accepts constraints as code. Other production solvers expect mathematical equations as input, even if they’re written in code. For example, to implement the constraint for a speaker to have a pause of at least 30 minutes between two talks, a Timefold model uses functional programming on Talk and Speaker classes, not code that specifies x + y <= 1. This makes writing new constraints and doing maintenance on them a lot easier in Timefold.
InfoQ: What are the hardware requirements of Timefold?
De Smet: Timefold is CPU bound. During solving, there is no I/O and most cases use less than 2GB memory. There is no training phase. In production, it’s typically run with 4 CPUs, for 30 minutes per dataset.
Big enterprises run 100 datasets per night across 5 hours, which use 40 CPUs.
InfoQ: What open-source options currently exist?
Janssen: There are several OSS libraries out there implemented by Google (OR-Tools) or Microsoft (Z3-Prover), mostly available in Python or C++. We had some presentations also at Devoxx from other solutions.
De Smet: There are a few libraries that come to mind written in the programming languages that timefold supports (Java and Kotlin) or aims to soon support (like Python).
In Java, there are a few like Choco-Solver, JaCoP, JOpt. In Python, there are several solvers written too: like CPLEX or COIN-OR.
Even though LLMs can help developers get to an easier solution by partially generating the model, for now, it is not possible to respond to the question "How can I schedule the talks for a conference?" So, experience and using tools like AI assistants will yield the most efficient solution both from the outcome and the resources point of view.