Variable neighborhood search accelerated column generation for the nurse rostering problem

The Nurse Rostering Problem (NRP) is an optimization problem where nurses with specific skills must be assigned shifts in a schedule. The objective is to obtain a feasible solution while minimizing the number of soft constraint violations. This work presents a Variable Neighborhood Search accelerated Column Generation procedure for the NRP in addition to a Relax-and-fix Heuristic for obtaining feasible solutions. The algorithm improved the best known solutions by at least 10% for all 29 hidden instances from the Second International Nurse Rostering Competition (2014) with 4 weeks. The improved solutions have an optimality gap of at most 8%.