Variable neighborhood search accelerated column generation for the nurse rostering problem

Abstract 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%.