Back around 2001 I made Tablix (https://www.tablix.org). It was my first larger open source project. Back then the faculty I was studying in had some really inconvenient timetables for students and I initially made Tablix to show that better scheduling of lectures was possible. It used a parallel evolutionary algorithm and was written in C. Code and everything else is still on-line but it's been abandoned for a long time.
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.
Oh yes, class scheduling is about the most political aspect of high school management. My dad is a retired high school teacher, and he served as a deputy director for several years. Part of the job is to make the schedules for everyone, and it was his most dreaded task every year.
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.
"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."
If you want to get an answer to your question, you should make it clear what exactly you do not understand in the statement I made.
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?
> 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
So teachers are expected to prepare and grade on their own dime?
teachers get a certain amount of prep time but its never sufficient and they do shit on their own time, all the time. plus they pay for school and class materials out of pocket routinely. I think in Ontario the average class is allocated like, $30 for the year in materials.
Teachers (at least in Spain) get a salary that covers class time and off-class duties. Most teachers don't hang out at school unless they have a reason to be there, or they prefer to work from their office, when they have one.
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.
Fun fact: ship scheduling in Rotterdam is a similar exercise in politics. I think the NextLogic centralized barge scheduling initiative started back in 2012 or so (https://www.nextlogic.nl/en/) and is only running in production for a handful of terminals and barge operators since the start of this year. Centralized planning is a bitch of a problem, not for technical reasons, but for political ones. I could go on and on about the various reasons parties did not want to participate, even though in principle everybody agrees that a centralized planning will be more efficient than every terminal doing it on their own.
Sounds like transit scheduling in the SF Bay Area. I forgot how many times I've seen a Caltrain depart just as a matching BART train was arriving in the station, just because they're separate agencies who technically coordinate some schedules, but in practice don't have any system constraints to enforce synchronized transfers.
When my sister graduated for her Electroengeering degree there was a fellow who wrote his master thesis about how to efficiently schedule bus lines.
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.
I don't understand;you're suggesting it would be more efficient to pickup/dropoff at random points in the city?
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?
I have an Industrial Engineering background and have used optimality solutions. The biggest hurdle I've found with "selling" optimality solutions is explaining the benefit. While it is great to show the technical and optimal savings it isn't always clear to the final user of the solution.
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.
We have been working with Optaplanner for the past 15 months. We switched from Drools to our custom score calculation rules and found it much easier to express business logic that way (on the one hand, we were unfamiliar with Drools and found the documentation unclear; on the other hand, our constraints are very complex).
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!
Thank for the analysis. You really get how OptaPlanner is not your father's solver!
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).
I gave up on Drools because I couldn't figure out how to read the error messages that came from it's half rule-language, half-Java compiler.
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.
Optaplanner has been widely known in the space for many years, funny to see it top on HN. It's awesome and scary in a Hibernate type of way. Huge, incredibly powerful, complex.
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.
Thanks for the kind words. We've working hard to reduce the complexity and will continue to do so. For example:
- 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
Constraint streams will be awesome! Writing constraints was the hard part, hard enough that eventually we gave up on a solver and went back to our terrible home rolled algorithm. That's always the case with solvers though.
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!
optaplanner simply rocks - I appreciate your work in the space tremendously.
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.
Yes, our container integration needs to become more streamlined. One of ours first goals is make it very easy to deploy all quickstarts on OpenShift (= Kubernetes) especially the Quarkus ones, by including a docker file and a how-to-deploy in the readme.
I haven't used OptaPlanner - what makes it better than Google OR-Tools, Gecode or other MiniZinc-compatible solvers?
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.
It scales better (for example in VRP we had case were OptaPlanner did in 5 minutes what Google OR-Tools did in hours), it can handle fairness and load-balancing constraints (= non-lineair constraints), it supports real-time planning (= changing the problem while solving it) and continuous planning, it uses OO input and constraint written in plain java (no math equations) and it integrates with the Java ecosystem (think REST, Jackson, JPA, Quarkus, Spring, ...).
It's much, much easier to use. We were able to get it working acceptably on a team with only algebra and basic calc knowledge. Really you don't even need that.
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.
Probably not your intent, but in my mind saying _anything_ is like Hibernate is equivalent to saying "run screaming in the other direction as fast as you can"
It's hard in the same way Hibernate is. If you don't fully understand it, things will end in disaster. It's still much more accessible than other constraint solvers which cater to math majors
Maybe lower level (but not the lowest), is minizinc. Def worth checking out if you don't want or need Java. A friend is using it for on-call schedule optimization - and wrote about the details here https://optduty.com/blog/2020-08-29-schedule-optimization/
As another commenter mentioned, MiniZinc is a DSL for modelling combinatorial optimization problems, and Google or-tools is a solver that can solve such problems. So it is not really comparable in that sense.
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.
Personally, I tend to use MiniZinc for prototyping and experimenting and for solving simple problems.
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/).
Basically this for me too; MiniZinc is great whilst you don't really have the full problem nailed, when it's harder to pick what you'd like to focus on using sovler wise.
I use Python to generate DPLL and likewise with MiniZinc. It’s no different from SQL: there’s something of an impedance mismatch that’s already felt in eg Sympy.
Minizinc is just a DSL for describing different models which is then compiled to flatzinc. Flatzinc is then accepted as input to a wide range of solvers, including Google OR.
Does anyone here have experience solving planning problems like these in Prolog?
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.
Declarative programming is very interesting. Some people are mentioning Prolog being slow. Well, I took an undergrad class on Prolog, and my perception is that Prolog can be very performant doing complete searches, but:
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.
I think the statistical methods would be better compared to a sat solver like Z3. Prolog gives you more flexibility, but it isn't going to be able to use the advanced search techniques that Z3 can take advantage of. Optimizers like Optaplanner are in sort of the same family as Z3, but they often trade being better at optimization for the ability to quickly find solutions, particularly if the number of solutions is small.
In my experience, seeing OptaPlanner pitted against the other best-of-the-best enterpise-grade solvers, OptaPlanner wins when scaling out - very clearly. Not when scaling down. This is the nature of the Local Search algorithms.
I think it very much depends on how hard your problem is. Small problems / search spaces will be fine in Prolog, but most realistic sized problems will quickly exhaust brute force search, and you will need to consider Local Search (like OptaPlanner), or Mixed Integer Programming, specialised Constraint Programming etc. There is a whole field of study on this - https://en.wikipedia.org/wiki/Discrete_optimization
Depending on which types of constraints you need to express your problem space, you could use plain Prolog or (more likely) make use of excellent constraint libraries like CLP(FD) for SWI-Prolog [1]. It's important to note that these are built into and tightly integrated with most Prolog. So people who point out that Prolog's backtracking search is too limited and/or slow are not taking the full picture into account.
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.
I’m not sure what the state of the art is, but certainly Prolog has been used for these kinds of things. Specialised dialects like ECLiPSe [1] have lots of options for solving constraint optimisation problems.
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.
> 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.
Prolog is a very different kind of system. It basically does backtracking natively, and everything else you have to build as libraries just like in any other language.
Looks interesting, this domain has a lot of players such as Google's coin-or so some quick description of its advantages or a benchmark would promote it better.
One strong advantage is how well it integrates with Drools so if you’re a Java shop and happen to be using Drools you can just drop in optaplanner and have it optimize around facts.
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.
Drools is awesome and we use it in some of our projects. but it just feels very monolithic and not a cloud native solution. What are some good lightweight alternatives to drools?
For decision tables, definitly look at Kogito and Drools-DMN as alternatives.
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).
we are working hard to deliver a stable version. stay tuned :) but it is still currently under heavy development. If you are interested in visually design rules, you might want to look into DMN!
Yeah, it does. If you want to learn more about it, check this: http://learn-dmn-in-15-minutes.com (it's a quick course I created to cover DMN on Kogito world)
Drools looks and sounds very good, but we already have a standard specification for workflow graphs called scxml and there are libraries which implement it and editors which can create it visually. I was hoping it would get more traction outside of Qt.
Not sure if you meant to have a comma in there or if you're incorrectly saying google made coin-or.
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.
>> OptaPlanner is an AI constraint solver. It optimizes planning and scheduling problems, such as the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more.
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?
Yeah, was generally aware that optimization ranging from (linear programming, MIP, genetic algorithms, PSO, simulated annealing, logic programming...etc) are generally considered to be in the AI group which also has everything from neural networks to gosh knows what.
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.
That's a good post, thanks for linking to it. It takes a good stab at answering "what is AI" (in the sense of what kind of computer techniques are AI), which is always a stickler. And it even has time for a very quick bit of history. I love it :)
I know about it but mostly because I had a professor who was really interested in all of this. I also think it is interesting that there has been quite a lot of improvements on this front without a lot of fanfare.
I think the reason is that these kinds of techniques are as old as nails. There's steady development but it's natural that there won't be as much excitement as for a fast growing (read: exploding) field as neural nets.
Whenever I see these things, I’m always reminded how amazingly hard deciding on constraints and utility functions can be. You want every employee to have a relatively contiguous schedule, but with at least a little break here and there, you want them to see the same patients as last time, wherever possible. You want everyone to get hours. Alice wants Thursday off, but she’s flexible. Bob commutes from Sacramento (we had to bring him in because we were short on his specialty) and really wants to be out in time to beat the rush. Patient X and therapist Y do really well together. And so on. And any imbalances need to be as fair as possible.
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.
There is an in-between option, at least for some use cases: Over time iteratively create a more complete set of constraints/heuristics, use them to generate one or more candidate solutions, and then manually tweak them.
Each round of iteration, look at which missing constraints caused the most manual tweaks, and improve from there.
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!)
OptaPlanner supports continuous planning (see my latest video), which is the ability to use a "sliding planning window".
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.
I also work at balena and often have a drifting non-24 hour sleep pattern, the schedule is generated once a week for the following week. You are free to change your working hours when ever you like and when the scheduler next runs it will take your preference into account.
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"
[disclosure: I work in this space and make another kind of optimizer.]
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.)
FWIW, OptaPlanner also works on Kotlin and Scala, not just Java. There is a 100% Kotlin variant of the quarkus-school-timetabling quickstart is also the optaplanner-quickstarts repo - and there's a video of that.
Some users have been successfully using OptaPlanner in jruby or groovy over the years, but your mileage may vary there.
Shameless plug nextmv (YC W20) https://nextmv.io/ is building tooling in the same space in Go and were cloud native / serverless first.
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).
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.
nextmv sounds like a breath of fresh air, congrats
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)
Maybe a bit lower level, but JuMP.jl [1][2] is an optimization library written in Julia that's starting to see a lot of usage (it's one of those libraries that's attracting people to Julia). Docs for setting up constraints in JuMP [3]
Optaplanner is a heuristic approach, meaning that you will not have any optimality guarantees until you have explored/filtered all of the domain. Gurobi is an MILP solver, relying on linear relaxations of the integer problem to provide you an optimality gap as you keep searching the tree and eventually a proof of optimality once you found one of the optimal solutions (there might be more than one that achieve the same objective, specially in scheduling)
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.