Polynomially solvable formulations for a class of nurse rostering problems

Identifying underlying structures in combinatorial optimisation problems leads to a better understanding of a problem and, consequently, to efficient solution methodologies. The present paper introduces a new network flow formulation for a large class of nurse rostering problems. By solving an integer minimum cost flow problem in a carefully constructed network, nurses' shift schedules can be constructed in polynomial time. The performance of the new formulation is compared with a state of the art algorithm on a benchmark dataset. Computational experiments show that the new formulation performs best both in terms of solution quality and computation time. By identifying inherent combinatorial structures which can be efficiently exploited, insight is gained into the problem's complexity, thereby laying the foundations for a theory of nurse rostering.status: publishe