How far can the nurse scheduling problem be solved with a non-commercial, i.e., free, optimization solver?

The figure below shows the results using Highs , which is considered the highest performance open source (non-commercial) solver. Benchmarks were made using Ikegami-3shift-Data1.1 by Dr. Ikegami.



“Highs” is included in Schedule Nurse as Algorithm 2, so it can be easily compared and measured on the same instance.



Algorithm 1 in the Schedule Nurse takes about 5 seconds to prove the optimal solution (objective function value 3). Algorithm 2 (Highs), however, could not reach the optimal solution even after 2 hours, and the objective function value after 2 hours was more than three times higher than the exact solution. In the end, even after 24 hours, the optimized value was never reached.

So, the results are not very promising in accuracy, quality, or time. As for the shift work schedule, here is how this performance difference affects the results.

(1) Even if the scheduling nurse can fulfill all vacation requests, they may not be fulfilled by the non-commercial solver.
(2) Even if a scheduling nurse can get all the requested assignments, a non-commercial solver may be unable to.
(3) It takes time for non-commercial solvers to make adjustments for better performance, such as trade-offs.

Free automated work schedule software may be a good option if you have ample human resources.
That’s because it means you don’t have the experience of struggling to get through requested time off or getting night, early, late, and day shift workers every day.
The problem is that
.

    1. is it the software's ability to find the answer?
    2. is it due to physical limitations?



There is no way to distinguish between the two.

Usually, commercially available scheduling software is not an optimization solver.
To say that something is “optimal,” you have to say that there is no better solution.
When the optimization solver knows that there is no better solution, it immediately terminates the search. This is because it knows that there is no point in spending any more time on it.

The basic strategy for a non-optimal solver is to keep searching because no matter how much time you spend, you do not know whether the current solution is optimal or not.
The difference in behavior is obvious, but the user probably does not know if the software you are using is an optimal solver or not.


Highs, SCIP, and CBC Performance Comparison

Comparison Results .

According to this , the amount of source code for SCIP is over 450,000 lines and that for CPLEX is over 600,000 lines. The optimization software has a mathematical and academic background. It is generally accepted that the performance difference between non-commercial and commercial software is about ten times. However, even if the software is non-commercial, it has a long history, starting with the CBC. The designer of Highs’ MIP solver is from SCIP, and the CBC was designed by John Forrest, who retired from IBM. And many of the commercial solver developers have SCIP backgrounds. Recently, the designers of the Highs MIP solver moved to the commercial solver FICO. The optimization software is a crystallization of the wisdom of mankind that has been nurtured over a long history. It is undoubtedly not something that can be done quickly.



Can the world’s best general-purpose optimization solver (MIP solver) solve the nurse scheduling problem?

The world’s best MIP solver is Gurobi . The progress of MIP solvers is tremendous, and it is reported that the performance ratio of MIP solvers in 2015 is 450 billion times higher than that of MIP solvers in 1991, when the performance of MIP solvers in 1991 was 1, including PC performance improvement. The performance ratio in 2015 was 450 billion times higher than that in 1991. And the results, which you can see here , are compared to the Schedule Nurse. The results are disappointing but still show that it is pretty solvable.
I think some companies are using the cloud to solve the nurse scheduling problem since the highest-performance commercial MIP solvers can solve the nurse scheduling problem quite well. It is an approach I would like to use if I could afford it (e.g., mounted as Algorithm 5), but unfortunately, it would be difficult to pay for it, even if I received ten times the current fee of 4.09USD/month or 4.09EUR/month.



So there is no non-commercial cue, then?

It may be possible if it is not a nurse scheduling problem or a small set of staff, probably less than 10.

The characteristic of the nurse scheduling problem is that it involves horizontal and vertically constraints.
If there are no or few horizontal constraints, then there is a possibility that it can be solved, even with an Excel solver.
In other words, if it is not the kind of work schedule for nurses and caregivers, I would say there is an excellent possibility that it can be solved. Also, a high-performance solver may not be necessary if the workplace has ample human resources.