Nurse scheduling problem with soft constraints

The Nurse scheduling problem is very challenging as it generally computes personalized schedules. The talk will focus on the deterministic version of the problem described in the INRC-II competition. One specificity is that most constraints are soft and thus can be violated at the price of a penalty. Classical branch-and-price algorithms underperform with soft constraints as they generally solve a classical resource-constrained shortest-path. In this talk, I will present a different approach to implement more aggressive domination functions for soft constraints, allowing to solve optimally many instances from the INRC-II involving up to 120 nurses and 4 shifts over a 4 to 8-weeks horizon.