Dissemin is shutting down on January 1st, 2025

Published in

Elsevier, Computers and Operations Research, 12(39), p. 3331-3343

DOI: 10.1016/j.cor.2012.04.018

Links

Tools

Export citation

Search in Google Scholar

A Constraint Programming based Column Generation Approach to Nurse Rostering Problems

Journal article published in 2012 by Fang He, Rong Qu ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Red circle
Postprint: archiving forbidden
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP-CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP-CG approach.