OptaPlanner – constraint solver for optimizing planning and scheduling problems
optaplanner.org
optaplanner.org
It was a mildly successful open source project around 2005 with a small community of contributors. The idea was that a school could boot a classroom of computers from bootable CDs and that would instantly create a cluster (using the PVM framework) that was then used to construct the timetable. High schools at the time were just getting equipped with such classrooms for teaching computer science.
I demonstrated it at a few institutions, applied for government grants and held some open workshops, but never was able to get any local school or faculty to use it. I learned that timetabling in institutions was as much a challenge in office politics as it was a technical problem. The largest successes that I can recall right now was that it was used in some published study of ship scheduling in the Rotterdam port and that I was paid by some Asian organization to develop some extensions they needed.
If I remember correctly one of the findings was that it would make sense to not let all buses start or finish at a bus/train station. I found that interesting. Maybe I can find it.
That would just decrease the stop-to-passenger effeciency in favor of passenger-to-walktime, but the optimization should be trying to favor the former?
Early in his career, it was done by hand, with large sheets of paper and moving cards around until all the pieces fit. Later, a couple of software companies came around, and they had this service where he would show up at an office, discuss the constraints with an operator, and choose among a handful options for the final schedule.
However, the crux of the problem was never the scheduling itself, but the accommodating of constraints which, given that teachers are in-class for 18-20h a week, but school is open for 30h/w, can get complicated pretty quickly. Some examples:
- Every teacher wanted to have one day with very light load, 1-2h max, so they could run other chores at home. Some people were very specific about this (i.e. they needed early Tuesday off), while others didn't care that much. - Nobody could just have a no-class day, due to administrative and legal reasons. - Having a gap hour without class was a big NO, because it adds to the time requirements without delivering actual teaching, so it was to be avoided at all costs. - All things equal, senior teachers outranked their junior peers in terms of choosing class levels, lab vs lecture, etc. - Some teachers had their own children attend the same school, and nobody wanted to teach their own kids (nor would the kids)
All in all, no matter how much time and effort he sunk into scheduling to everyone's liking, there was no perfect solution, and every single year there were aggravated teachers who would raise hell. He was called inhumane by someone who claimed the right to a free hour every morning to drop off her own kid, but only got her wish 4 days out of 5. He had peers stop talking to him over class level choices. The only reason he kept doing it was because the director was his close friend, and he asked my dad repeatedly. But he didn't wish that job on his worst enemy.
So teachers are expected to prepare and grade on their own dime?
The problem with a gap hour (from the point of view of a teacher) is that it forces the teacher to stay in school when they don't necessarily have to. It reduces flexibility in their schedule.
https://www.reddit.com/r/todayilearned/comments/14ucj2/til_b...
"Bill Gates was recruited to write the class scheduling software for his high school. He used that power to place himself in classes with more female students."
We somehow tend to think that these things don’t matter but this is exactly the kind of small things that corrupt our governments.
Do you disagree with the premise? Do you think that what Bill Gates did wasn’t actually fraud? Do you think that a politician behaving like that on a daily basis is not the essence of corruption?
The best way to "sell" the solution is to translate it to real savings that the end user understands. For instance if it is a public municipality show them how much time is saved to open up resources. For private institutions show them how much money is saved that will improve profits or reduce costs.
One of the greatest features of Optaplanner with respect to alternatives, such as OR-tools, MiniZinc and the likes, is that you can express your rules in plain Java, which anybody with an imperative programming background can figure out (this is partially due to the simplicity of the Local Search model that Optaplanner is based on).
Most other tools function differently: most fundamentally, they do not use Local Search but rather Constraint Programming or Mixed Integer Programming. This means they offer you a way to encode your constraints by providing a variety of patterns for the various types of constraints they support. We found that this approach is generally harder (it requires a different mindset at the very least) and requires far more planning in advance when deciding how to represent your variables. We couldn't afford this as our process of requirements discovery went on for well over a year.
All in all, I would recommend Optaplanner. And props to Geoffrey who is helpful and responsive on various platforms!
It is a team effort. Credit is due the rest of the team too (Lukas, Radovan, Jiri, Christopher, Julian, Karina, Duncan, Michal, Anna, Emily, Michael, Mario, ... and everyone I am forgetting to mention).
There are other rule languages where I find the error messages hard to read (Jena Rules, clara) but in those cases I can read the source of the compiler and/or run it in the debugger to understand what is going wrong and it would take me too long to figure out how to do that with Drools.
It's the only framework of its kind for constraint optimization. Nothing else comes close to the flexibility at high level Optaplanner offers. I would bet over 50% of commercial software that does optimization over NP-hard problems is using optaplanner.
On the commercial NP-hard optimization front Gurobi, CPLEX and to some extent XPRESS are surely formidable as well. Of course mixed-integer solvers don't always directly compete with constraint programming solvers, since some problems are better solved with one or the other kind of solver.
YMMV, I am very biased.
It's more automatic and focuses on good performance out of the box, with custom solver phases and such only recommended if you have performance problems.
Its also fully object oriented. The solver works on Java POJO's
In addition, it has built in tools for unit testing and detecting score corruption.
It's very much on the practical, rather than theoretical end of solvers. You can drop it into an existing Java project with zero fuss.
- ConstraintsStreams (instead of DRL) to declare incremental constraints easily in plain Java (or another JVM language). No need to learn the Drools Rule Language any more.
- Autoconfiguration (no need for solverConfig.xml unless you want to power tweak) thanks to our Quarkus extension or Spring Boot starter.
- SolverManager that manages Solver threads for you. Great to avoid HTTP REST timeouts or to solve multiple problems.
Coming soon:
- Code completion (XSD) when power tweaking the solverConfig.xml
- Simplified VRP model
My suggestion is to create a simple way to deploy a to containers so that a primary server can pass out parallel optimization runs to a set of secondary nodes, allowing you to parallelize really easily.
a second generation of this would include code to spin up secondary nodes on demand depending on the number of parallel scenarios you want to run.
Today, it should already just be a matter of taking the quickstart(s): https://github.com/kiegroup/optaplanner-quickstarts and following the quarkus deploy guide: https://quarkus.io/guides/deploying-to-openshift but we'll streamline it even more.
As a second stage goal, this will deal with starting up nodes as needed too.
Another hard part was combining chain through time with entities that can be scheduled together vs ones that need gaps. This seems to be a common use case, grouping work where you need a setup/teardown gap between entities. Not sure how to improve this but maybe add some kind of built-in support for "entity coloring" on chained variables where you can configure which run together in a chain vs which ones need setup/teardown gaps between.
Overall Optaplanner is an amazing piece of software though, good work!
https://www.minizinc.org/challenge2020/results2020.html
Is it more customizable? Or expressive (in terms of modeling DSL)?
The benefit of using MiniZinc instead of a specific solver directly, is that the user can try different solvers easily to find the one that works best for their problem. The drawback is naturally that it may be harder to use solver specific features.
The MiniZinc challenge is a competition that pits these solvers against each other. Note that the group that runs the challenge also develops solvers (which are ineligible to win prizes in the challenge, but are participating), and that these solvers are sometimes better than Google or-tools (no solver dominates all other solvers). See https://www.minizinc.org/challenge2020/results2020.html to get the full results.
Finally, while solving speed is of course important, it is not always the most important issue when developing a cobinatorial optimization solution. Choice of general tech stack, documentation, support, ease of integration, local expertise, and so on are important issues, as it is for every large dependency choice.
Their DSL look very similar to a lot of specific DSLs of other tools in the field
As opposed to OR-Tools where you can directly use a language you know (like Python) to express your constraints and targets
Having worked with both approaches, I like the latter better
For building larger solutions, I would also probably use a solver directly. Reasons for that would be customization, integration, and data handling issues. For me the go-to system would be Gecode, but there are a lot of very interesting and varied solvers available.
Worth noting is that MiniZinc is starting to get more and more support for integration into large systems, for example with the python interface (https://pypi.org/project/minizinc/).
For the delivery company example mentioned on the site, I’d imagine a database, perhaps just ‘library(persistency)’, storing the fleet of cars the company has, the delivery orders, the drivers employed, etc. The constraints would be expressed as prolog relations.
I may be implementing a system like this soon, and would like to hear war stories of doing it with a library like OptaPlanner or Prolog.
I think the biggest challenge in optimization problems is converting the constraints from object/concept space to integer/constraint space and back. Once you're done with that, it doesn't really matter which tools you use as long as they provide the mathematical operations necessary.
Once he had to convert a Prolog algo in 50 `if then` in C. He told me it wasn't clean but the perfs they got out of it was an order of magnitude.
Then you may want to also dig into https://en.wikipedia.org/wiki/Answer_set_programming papers / solvers / systems over the past ~1.5 decades or so.
> In a more general sense, ASP includes all applications of answer sets to knowledge representation and the use of Prolog-style query evaluation for solving problems arising in these applications.
1) You need to know how to encode the constraints so they can be evaluated efficiently, not just write them.
2) A common way to achieve 1) is to encode a problem as a SAT problem and use a modern SAT solver. They are pretty sick. You can write great SAT solvers in Prolog, but there are already many good ones in many languages, so it's quite poinless unless you do it for fun or learning.
3) Compared to most statistical methods / heuristics, searches in Prolog will be slow. And in most cases statistical methods will do fine anyway, because there will be at least decent solutions to be easily found.
My conclusion is that we often confuse the problems of "proving that a plan is optimal" with "finding a good plan", which are indeed related, but use very different techniques to reach solutions.
The bigger the search space, the more we like it.
I also recommend checking out Picat, a Prolog-derived language with excellent support for constraints programming and many built-in global constraints (a very important tool for larger-scale constraint programming) [2]. As of the recently released version 3 (featured on HN [3]), Picat also supports traditional Prolog syntax. IMO Picat is still rough around the edges when it comes to error messages, modularization etc, but if nothing else it's excellent for learning and for prototyping constraint models.
[1] https://www.swi-prolog.org/man/clpfd.html [2] http://picat-lang.org/ [3] https://news.ycombinator.com/item?id=24608997
Because it’s Java you can use it with all the various libraries and any compatible languages that support Java libs like kotlin and Scala.
Is Kogito ready for production use? Does it have a UI that lets users develop their own rules?
To declare incremental constraints in OptaPlanner, take a look at ConstraintStreams if you want to avoid learning DRL: https://www.optaplanner.org/blog/2020/04/07/ConstraintStream... It's very similar to Java 8 Streams (but incremental and under the hood it uses Drools).
[0]: https://www.coin-or.org/ [1]: https://developers.google.com/optimization/
Coin-Or is a separate project. It's the fastest free/open source LP & MILP solver I've seen, but has a terrible CLI if you don't want to use it as a C++ library. It's easiest as part of the Open Solver Excel plugin. Lp_Solve isn't as fast I don't think, but the CLI is much easier to use and better documented. I prefer to use a scripting language language to write my own .lp models and send that directly to the solver. There are lots of libraries to do that, but it's easier for me to write code I fully understand than to try to learn someone's library.
Google has the "Or-tools" solver which I haven't used, but have friends which do use it and like it.
Just today I was moaning to my thesis advisor that most people entering AI today don't really know the history of AI before ca. 2012. He told me about a researcher he knew back in the 1970's who used to complain about the same thing exactly in machine learning meetings they had back then.
In any case, I wanted to ask- folks on HN who are interested in machine learning (or actively working in the field, one way or another), did you know that there is a thing such as "planning" (or "constraint solving") and that it's a part of AI?
I think AI is just one of those hard to describe terms. I remember sitting around with some friends over a decade ago arguing over what a "hipster" was lol. That's another term that is a little nebulous.
SHort answer: Local Search is in the AI bible (AI a modern approach by Russell and Norvig), so OptaPlanner is part of AI.
Long answer: It depends how old you are. See https://www.optaplanner.org/blog/2017/09/07/DoesAIIncludeCon...
https://docs.optaplanner.org/7.44.0.Final/optaplanner-docs/h...
When I was spec’ing out a project to help a friend save time doing the schedule manually, I realized that it would be more work to enter the constraints/goals than to just do the schedule manually. Or you save a ton of time on the schedule without capturing all the knowledge and judgement a person doing it manually has, and just have things a little worse for everyone (and maybe much worse for a few unlucky folks).
I wonder how often, when systems like this get into production, running employees lives, the implementer just decides the automation savings are worth it and it’d be too hard to formalize the human part, so they just don’t.
Each round of iteration, look at which missing constraints caused the most manual tweaks, and improve from there.
https://www.balena.io/blog/the-unreasonable-effectiveness-of...
I've been struggling with an issue myself where I have a non-24 hour sleeping pattern. Does your system handle changing of timezones gracefully? It's almost like my timezone changes by 1.5-2hrs every day, and sometimes stressful days will completely throw it off.
Figuring out how to stay in sync with a 24-hour world has been a thorn in my side for ages and I think planning like you're doing would help me tremendously. (I actually clicked to read the comments on optiplanner to do something very similar to what you've been doing!)
So if go nocturnal you can shift your work hours to the night and the scheduler will try its best. But there is another constraint which is your colleagues work hours, your hours should have some overlap with theirs so that the schedule is "solvable"
It also supports the use of java.time, which means it supports LocalDateTime, OffsetDateTime, ZonedDateTime, and all other time related functionality that deals with implementing the insane intricacies of time for you. For example: if a shift runs from you 2:00 UTC to 10:00 UTC and employees from different timezones can furfil it and Daylight Saving Time changes for one of those employee's regions, you can write a constraint to detect that and avoid assigning the DST-affected employee that night.
Sorry to talk about a competing product here...
We've been applying deep reinforcement learning to various scheduling problems (which are hard!), and it has shown performance gains of between 10% and 32% on various use cases.
The thing that RL can do, which mathematical solves sometimes struggle with, is generalize for highly variable data, and be updated quickly. (You can retrain the policy without rewriting anything manually, unlike MIPS.)
We're doing that here:
We're automating several steps in RL, including choosing the architecture and the hyperparameters.
https://pathmind.com/why-pathmind/
Anyone who would like to learn more should feel free to message me.
Our goal is to encourage and benchmark the progress of MARL methods to manage dense traffic on railway networks.
Some users have been successfully using OptaPlanner in jruby or groovy over the years, but your mileage may vary there.
See section 2.2: https://docs.optaplanner.org/7.36.0.Final/optaweb-vehicle-ro...
You can still call it from JVM using JNI
I used optaplanner at a previous gig before working at nextmv — we don’t offer the same type of “choose your own adventure” tooling compared to optaplanner yet, but it’s much more lightweight to get, say, a routing model shipped in to production IMO. (Java shops notwithstanding).
I would have maybe liked Optaplanner if I could peer through all the layers of Java, it seems like a thick Java sandwich with some optimization somewhere (but I have to say I lost it when you can turn your model into XML apparently)
Nextmv has just the right level of abstraction needed for software engineers. Took us very little time to get a production model running.
The -Dnative build compiles your java code natively into an native executable that boots up in milliseconds (instead of seconds like a JVM). This is the result of strong collaboration between us (the OptaPlanner team) and the Quarkus team and we have more features in the pipeline.
[1] https://jump.dev/JuMP.jl/stable/
[2] https://github.com/jump-dev/JuMP.jl
[3] https://jump.dev/JuMP.jl/v0.21.1/constraints/(or is it mainly a question of Java ecosystem vs rest of the world?)