Most people who try to make a duty roster generator probably started with the OR-TOOLS Employee Scheduling Example — me included.
OR-TOOLS is an excellent open-source Constraint Programming (CP) software developed by Google to solve problems that can be expressed as constraints, such as duty rosters.
But OR-TOOLS is not the only way you can make duty roster generators.
On the other spectrum we have Mixed Integer Programming (MIP), which can generate an optimal solution under a set of linear inequalities as constraints.
The state-of-the-art commercial MIP solvers include Gurobi, CPLEX, Xpress, and some open-source solvers such as CBC, HiGHS, SCIP, etc.
Here comes the big question.
Which approach is better when it comes to Duty Roster Generation?
That’s the question we’re going to tackle today.
Constraint Programming (CP)
CP originated from the AI field, where there are many high-level, non-linear constraints.
Decision variables are defined and live in some domain (e.g. real numbers, integers, binaries, etc.), and they’re forced to obey a set of commands.
For example, one would usually generate a matrix of binary variables indexed by the staff, date, and shift type. If the variable value is 1 it means the person is on duty, and if it is 0 then the person is off duty.
The solver then uses methods such as chronological backtracking and constraint propagation to find a feasible solution for the problem.
Some CP solvers allow for the user to define a certain objective value. The CP algorithm would then compare feasible solutions and output the one with the better objective value.
Advantages as a Duty Roster Generator
Very Versatile Constraints
A major advantage of CP is the level of versatility it provides. For example, let’s say I have a rule like this:
Each Operation Theatre requires 1 anesthesiologist. The anesthesiologist can bring along their trainee. If manpower is insufficient, the anesthesiologist can take care of 2 rooms at once but cannot take their trainee with them.
Such a rule is notoriously hard to implement in MIP, since it requires conditional constraints — the anesthesiologist can’t bring on a trainee only if they don’t have enough staff to cover every operation theatre.
(Note that it is still possible to model something like this in a MIP, but it requires the use of numerous auxiliary variables, which adds one layer of additional complexity)
The key word here is Logical Constraints. CP formulations are much more versatile if your roster rules contain a lot of logic like the above constraint.
Quick First-Feasible Solution
CP solvers, due to how their engines are modelled, are generally superior to MIP at finding feasible solutions to a problem.
In other words, if your roster rules are extremely constrained, you may consider using CP models over MIP models.
Mixed Integer Programming (MIP)
MIP, like CP, defines variables in various domains, which are fitting for a rostering problem.
MIP solvers are different in that they use techniques such as branch-and-bound, branch-and-cut, and LP relaxations when they solve the problem.
In very non-technical terms, most of them try to
- Allow integer variables to take continuous values (for now), which gets them a solution that sits very close to the optimal solution.
- The solution is usually invalid because you need some of the constraints to be integers. In this case, you force one of the variables to take integer value, then solve again.
- Repeat, repeat, repeat. Until you find the best solution.
Advantages as a Duty Roster Generator
Better Objective Values
Remember how CPs iterate through feasible solutions and give you the solution with better objective?
Instead of looking at each possible solution, MIP solvers go straight to the best, but usually invalid solution (which we call the LP relaxation). This means that if you’re aiming for a good objective value, MIPs are usually better.
Proof of Optimality
MIPs can tell you, with 100% certainty, that they’ve found the best possible solution.
This is because they can compare their incumbent (current best) solution anytime with the theoretical best solution (lower bound if you’re minimizing).
This is often not possible with CP, especially with larger problem size. Because they would need to really iterate through every possible solution to find the optimal solution.
That said, the optimality guarantee is often dependent on time limits and problem size. For large or complex problems, MIPs might not find the optimal solution within practical time limits, while CP might provide good feasible solutions faster.
Which one should I choose for a Duty Roster Generator?
As a matter of fact, most roster problems can be modelled in both CP and MIP. The main differentiator is the speed to solution and the quality of the solution.
I want a solution for my duty roster fast, and don’t care the quality as much.
Go for CP. It gives you feasible solutions faster.
I want the best solution for my duty roster, or at least, I care about the solution’s quality.
Go for MIP. It will usually give you a better solution.
If your problem is small, you can still go for CP, since it can iterate through all the possibilities pretty fast.
I have super-duper complex logical constraints for my duty roster.
Go for CP. It lets you build more versatile constraints. However, with the right techniques, you can also build complex logical constraints into MIP.
Practical Concerns
When choosing between CP and MIP, speed and optimality are not the only considerations. Factors such as ease of implementation, availability of libraries, or community support might also influence the decision.
Choice of Solver
Another factor is the solver you use.
There are countless competent solvers for both CP and MIP. While CP and MIP are frameworks to model your problem, you still require solvers to run your model and get the solution.
You will get vastly different outputs depending on the solver you use. There are online benchmarks for MIP solvers, for example, the Mittelmann Benchmark, which you may refer to for choosing the appropriate MIP solver.
Not only that, but the performance of a specific solver can also vary dramatically based on the problem formulation. The choice of formulation can significantly impact the efficiency and quality of the solution, regardless of the approach used.
This is why MIP and CP model formulation sometimes requires a high level of technicality.
Disclaimer: At the end of the day…
These are all theoretical discussions. There will be always types of problem where CP struggles to find a feasible solution when MIP does it under 1 second. Or vice versa.
Knowing when to choose which toolkit requires experience and skill. However, before actually putting it to the test, no one can ever guarantee you which is better.
In practice, the quality of your formulation often matters more than the solver you use, or even, whether you went for CP or MIP. Especially, if you see a slow solver behavior in small problems, it is likely a matter with your formulation that it is with the solver.
Optimize Your Duty Roster with Expert Assistance
Our Duty Roster Scheduling Service
If you’re looking to implement an efficient, fair, and compliant ward roster scheduling system, we can help. We offer personalized algorithm development and web-based solutions tailored to your specific needs. Learn more about how we can transform your scheduling process.
Learn to Schedule Duty Rosters with Program
If you want to try making your own rostering algorithm, you can learn it with my free e-book. This guide introduces you to the basics of using programming to create efficient and fair schedules. You will learn how to translate ward rules into code, automate repetitive tasks, and generate optimized duty rosters with ease. Because most doctors have little programming experience, I’ve written it for beginners in Python. Download it and start learning now!
Follow Us for More Insights!
I post regularly at my LinkedIn. Follow me for more updated programmatic rostering insights!