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 efﬁciency 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 efﬁciency of
the hybrid CP–CG approach.