Sounds more like a classic optimization model (operations research) than like an AI model. Great case study though. I wonder why they used a GA and custom stuff instead of off the shelf software from gurobi or IBM OPL etc.
For scheduling problems, I have had way more luck with open source CP solvers like Choco than I have had with hyper-optimized commercial IP solvers like gurobi. Branch and Cut is just too indirect for constraint heavy IP models.
"Nurse scheduling competitions" seem to alternate between IP and CP approaches - my feeling is that when the number of solutions is "small", CP pulls ahead, but when there are many solutions and the objective is important, IP wins. Very case-by-case dependent, regardless.
I've found that size doesn't matter much at all...but constraint type does (hard vs soft). Soft constraints very easily lend themselves to IP formulations, but problems with lots of hard constraints require a ton of luck to get it to work quickly with an IP solver. 3d bin packing, for example, is very heavy on hard constraints. I have a CP model (using the Geost constraint primarily) with an ensemble search heuristic (genetic + LNS), and I have yet to find an IP model that can get within 2 orders of magnitude of the average solve times of the CP model.
