When you turn a roster into a mathematical model, you’re bound to choose a solver to solve your problem.
However, there are many solvers out there, and it’s hard for a beginner to recognize which is the best for them.
We’re here to demystify them today.
What types of solver are there?
Welp, there are many classifications (just like diseases), which we will go through one by one:
1. Classification By Problem Type
Mathematical models are not all built the same. Depending on the types of variables, constraints and objectives, here are the most common formulations.
- Linear Programming (LP):
- All variables must be real, continuous numbers.
- All constraints and objectives must be linear.
- Mixed Integer Programming (MIP):
- Some variables can take integer (or binary) values.
- All constraints and objectives must be linear.
- Quadratic Programming (QP)
- All variables must be real, continuous numbers.
- All constraints must be linear, but the objective may be quadratic.
- Mixed Integer Quadratic Programming (MIQP)
- Some variables can take integer (or binary) values.
- All constraints must be linear, but the objective may be quadratic.
- Mixed Integer Quadratic Constraint Programming (MIQCP)
- Some variables can take integer (or binary) values.
- Constraints and objectives can be quadratic.
- Non Linear Programming (NLP)
- All variables must be real, continuous numbers.
- Constraints and objectives can be nonlinear.
- Mixed Integer Non Linear Programming (MINLP)
- Some variables can take integer (or binary) values.
- Constraints and objectives can be nonlinear.
Summary
| Problem Type | Variables | Constraints | Objective | Solver |
|---|---|---|---|---|
| Linear Programming (LP) | Continuous | Linear | Linear | Gurobi, CPLEX, Xpress, GLPK, cbc, HiGHS, GLOP |
| Mixed Integer Programming (MIP) | Continuous/integer | Linear | Linear | Gurobi, CPLEX, Xpress, cbc, HiGHS |
| Quadratic Programming (QP) | Continuous | Quadratic | Quadratic | Gurobi, CPLEX, Xpress, MOSEK, IPOPT, HiGHS, CVXOPT |
| Mixed Integer Quadratic Programming (MIQP) | Continuous/integer | Linear | Quadratic | Gurobi, CPLEX, Xpress, MOSEK, IPOPT, CVXOPT |
| Mixed Integer Quadratic Constraint Programming (MIQCP) | Continuous/integer | Quadratic | Quadratic | Gurobi, CPLEX, MOSEK, Octeract, Xpress, ANTIGONE |
| Non Linear Programming (NLP) | Continuous | Non Linear | Non Linear | ANTIGONE, CPLEX, Gurobi, Ipopt, SCIP, Xpress |
| Mixed Integer Non Linear Programming (MINLP | Continuous/integer | Non Linear | Non Linear | QPOPT, ANTIGONE, BARON, Couenne, SCIP, Octeract |
Roster problems are combinational problems, which means the solution is discrete: one person either takes this shift, or that shift, or he is not at work.
This means that our variables must take at least integer (or binary) variables, so the problem types we can model our roster problem are: MIP, MIQP, MIQCP, and MINLP.
2. Classification by Commercial/ Open Source
Ha! Money stuff. Unlike in the realm of machine learning, where open source tools are winning the game, in Operations Research, there are some commercial solvers available.
In general, commercial solvers are faster than the open source solvers (because they have dedicated mathematicians working on them), however, it also costs a lot more.
In the contrast, open source solvers are free to use (at least personally). But their speed to solution, and sometimes, the solution quality, is in general less performant than the dedicated commercial solvers.
Here are some most commonly used commercial & open source solvers:
| Commercial | Open Source |
|---|---|
| Gurobi | GLPK |
| IBM CPLEX | cbc |
| FICO Xpress | HiGHS |
| MOSEK | SCIP |
| Knitro | CVXPY |
| AMPL | OR-Tools |
How to Choose Between Solvers?
You’ll ask yourself some questions first:
Are you affiliated to any university or college?
Some solvers (such as Gurobi and CPLEX) offer academic licenses. As long as you don’t use them for profit, you can use them for free.
If not, you probably don’t wanna pay for solvers anyways, so your best bet is with the open source solvers.
How Will You Model Your Roster?
As we said above, the only relevant solvers for rostering are those that allow integer variables. So, MIP, MIQP, MIQCP, or MINLP solvers are what you’re looking at.
Most roster rules are linear (such as “2 staff required per shift”, or “each staff works at most 1 shift every 3 days”).
Sometimes you’d need to minimize something like “variance of total shift number” across staff, to make shift assignments fair. You can do that with quadratic formulations. Alternatively, you can linearize your objectives and make them linear with some special modelling techniques.
But I don’t suggest going anywhere towards MINLP.
Because MIP problems have some numerical properties that MIQP don’t have, solvers often leverage that to their advantage, resulting in faster solves.
The same applies for MIQP solvers, when compared to MINLP. The more complex you allow your problem to be, the fewer tactics solvers can use to attack them. This results in the solver becoming less performant.
For the same MIP, MIP solvers would perform much faster than MINLP, due to the leverages they have. Therefore I’d suggest you code your problem in a less complex way, such as MIP or MIQP, to avoid this problem.
MINLP is still ok, but only if you know what you’re doing (and that you know there is no way you can reduce that problem into a MIQP or a MIP).
Which Solver Performs the Best?
The Mittelmann Benchmark, by Hans Mittelmann, benchmarks across different solvers specializing in different model types, and is an excellent reference for you to choose your solvers.
Recently there had been some actions from Gurobi and FICO Xpress to remove themselves from the benchmark, but Mittelmann still represents a very valuable reference, nonetheless.
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!