A rotation-based branch-and-price approach for the nurse scheduling problem

International audienceIn this paper, we describe an algorithm for the personalized nurse scheduling problem. We focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition. One specificity of this version of the problem is that most constraints are soft, meaning that they can be violated at the price of a penalty. The feasible space is thus much larger, which involves much more difficulty to find the optimal solution. We model the problem as a an integer program (IP) that we solve using a branch-and-price procedure. This model is, to the best of our knowledge, comparable to no other from the literature, since each column of the IP corresponds to a rotation, i.e., a sequence of consecutive worked days for a nurse, and not to a complete individual roster. We tackle instances involving up to 120 nurses and 4 shifts over an 8-weeks horizon by embedding the branch-and-price in a large-neighborhood-search framework. Initial solutions of the large-neighborhood search are found by a rolling-horizon algorithm, well-suited to the rotation model