OptaPlanner

To OptaPlan or not to OptaPlan: That was my question. And ultimately, the answer came back as (drum roll please)… don’t OptaPlan.

The Problem

What am I talking about here? I was working on a project where I needed to solve this problem: I needed to be able to generate study schedules for college students. For example, say you’re enrolled in four courses and you need to come up with a study schedule for your homework, exams, term papers etc. for the entire semester, given the constraints of your sleep time, wake time, meal times etc. At first blush, it seemed clear to me that I needed to sit down and write an algorithm for this. However, after speaking to one of my illustrious higher-ups, I found out that this was a solved problem. Enter OptaPlanner.

OptaPlanner

OptaPlanner is a sophisticated and robust Java library that can be used to solve precisely these types of problems. If you give it a series of “blocks” that need to be laid out in a calendar, and tell it what constraints it needs to respect (e.g. in my case, wake time, sleep time etc.), it can generate an optimal schedule for you. No need to write your own custom algorithm. And it can do a lot more than that; basically any type of problem that requires entities to be arranged in a certain fashion can be solved using OptaPlanner. An example problem in the OptaPlanner test suite is the NQueens problem, which entails laying out N number of queens on a chessboard such that none of them can attack each other (for example, arranging 4 queens on a 4 x 4 chessboard in this fashion). OptaPlanner can do this for you.

Pros and Cons

Well that’s frigging shweet!! So what the problem is?? There are some considerations here:

1) Learning curve. Using the library is no joke. You can’t just pass in a list of study blocks, a list of constraints and say “Go forth and schedule.” You first have to explain to OptaPlanner exactly what problem you’re trying to solve. You have to create “planning entities” (i.e. the entities to be arranged, which in my case were study blocks). You have to create “value ranges” (i.e. the spots where entities can be placed, which in my case were the time slots in which study blocks could be scheduled). The “planning entities” and “value ranges” are housed in a “planning solution”. You can then (optionally) create an initial solution of your own which OptaPlanner will optimize. And ultimately, you have to write a “solver”, which is what OptaPlanner passes its proposed solutions through in order to see how well they match your specified criteria. (And you can write your solver using plain ole’ Java, or, if you want to take another learning curve hit, you can write it in Drools, which has far better performance.)

That was just the set up. Now comes the configuration. The number of ways in which OptaPlanner can be optimized is overwhelming. What OptaPlanner does to solve your problem is basically run a series of simulations, trying one arrangement after another, until it finds one that comes closest to matching all your criteria. This can take a long time. A looooooong time, depending on the size and complexity of your problem. So OptaPlanner has myriad configuration options to try to solve the problem in a reasonable time frame. You can have no initial solution, or you can create your own initial solution, or you can employ one of a number of different construction heuristics to create an initial solution. Then, pick an algorithm: hill climbing, tabu search, simulated annealing, late acceptance, or step counting hill climbing. Or try one of the experimental evolutionary algorithms if that’s what you fancy. You can pick from 6 different types of move selectors. In my case, nothing was performing fast enough, so I tried a different approach: I implemented a custom move selector, which, as you might imagine, is a learning curve in itself. You can also implement benchmarking to find out which particular combination of options might be the fastest. And of course, I’ve just gone over the meat of the options here; there are still many others.

2) Performance. This is ultimately why I abandoned OptaPlanner: my problem size was simply too large, and I couldn’t get it to find a good solution in a reasonable amount of time. When I say “my problem was too large”, I mean that I had a 4-month calendar that was divvied up into 5-minute time slots, which yields about 35,000 potential scheduling spots. Several hundred blocks needed to be scheduled in this space, and the number of constraints that needed to be met grew and grew as time went on. I ultimately needed a schedule to be generated in maybe 5 – 10 seconds tops, but I was seeing times that were many orders of magnitude above that.

3) Determinism. OptaPlanner is not deterministic. With OptaPlanner, you specify some max amount of time that it should run for, let’s say a minute. It will run as many simulations as possible in that one minute and give you its best solution at the end. But two different runs will not always produce the same result.

Bah… Screw It

All things considered, I ended up having to abandon OptaPlanner. I wrote a custom scheduling algorithm that is deterministic, far quicker (roughly 5 seconds, which is still quite slow; plenty of room for optimization there), and just far easier to modify.

Based on what I saw, OptaPlanner is an incredible library, but perhaps for certain types of problems. Perhaps if you have a complex problem that doesn’t need an immediate solution, i.e. one where you could background the task, this would be well-suited. Or perhaps it would be ideal if you have a problem that is simply too difficult to solve by writing your own algorithm. OptaPlanner would be perfect for that because it simply runs simulations. But for me and my life and my world and my particular situation… I had to bid adieu to OptaPlanner, with a heavy heart. Sniff… goodbye OptaPlanner. I’ll never forget you.