A Constraint Programming based column generation approach to nurse rostering problems

He, F. and Qu, R. 2012. A Constraint Programming based column generation approach to nurse rostering problems. Computers and Operations Research. 39 (12), pp. 3331-3343. doi:10.1016/j.cor.2012.04.018

TitleA Constraint Programming based column generation approach to nurse rostering problems
AuthorsHe, F. and Qu, R.
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.

KeywordsColumn generation; Constraint programming ;Heuristics; Nurse rostering problems; Scheduling
JournalComputers and Operations Research
Journal citation39 (12), pp. 3331-3343
ISSN0305-0548
Year2012
PublisherElsevier
Digital Object Identifier (DOI)doi:10.1016/j.cor.2012.04.018
Publication dates
Published21 Apr 2012

Related outputs

Modelling the Home Health Care Nurse Scheduling Problem for Patients with Long-Term Conditions in the UK
He, F., Chaussalet, T.J. and Qu, R. Modelling the Home Health Care Nurse Scheduling Problem for Patients with Long-Term Conditions in the UK. 33rd International ECMS Conference on modelling and Simulation. Universita degli Studi della Campania, Caserta, Area of Napoli, Italy 11 - 14 Jun 2019

Controlling Understaffing with Conditional Value-at-Risk Constraint for an Integrated Nurse Scheduling Problem under Patient Demand Uncertainty
He, F., Chaussalet, T.J. and Qu, R. 2019. Controlling Understaffing with Conditional Value-at-Risk Constraint for an Integrated Nurse Scheduling Problem under Patient Demand Uncertainty. Operations Research Perspectives. 6 (2019), p. 100119. doi:10.1016/j.orp.2019.100119

Hybridising local search with Branch-and-Bound for constrained portfolio selection problems
He, F. and Qu, R. 2016. Hybridising local search with Branch-and-Bound for constrained portfolio selection problems. 30th European Conference on Modelling and Simulation (ECMS 2016). Regensburg, Germany 31 May - 01 Jun 2016

A compromise based fuzzy goal programming approach with satisfaction function for multi-objective portfolio selection
He, F., Qu, R. and John, R. 2015. A compromise based fuzzy goal programming approach with satisfaction function for multi-objective portfolio selection. 29th European Conference on Modelling and Simulation (ECMS 2015). Albena, Bulgaria 26 - 29 May 2015

A Hybrid Genetic Algorithm for a Two-Stage Stochastic Portfolio Optimization With Uncertain Asset Prices
Cui, T., Bai, R., Parkes, A., He, F., Qu, R. and Li, J. 2015. A Hybrid Genetic Algorithm for a Two-Stage Stochastic Portfolio Optimization With Uncertain Asset Prices. IEEE Congress on Evolutionary Computation (IEEE CEC). Sendai, Japan 25 - 28 May 2015 IEEE . doi:10.1109/CEC.2015.7257198

A two-stage stochastic mixed-integer program modelling and hybrid solution approach to portfolio selection problems
He, F. and Qu, R. 2014. A two-stage stochastic mixed-integer program modelling and hybrid solution approach to portfolio selection problems . Information Sciences. 289, pp. 190-205. doi:10.1016/j.ins.2014.08.028

A constraint-directed local search approach to nurse rostering problems
He, F. and Ru, Rong 2009. A constraint-directed local search approach to nurse rostering problems. 15th International Conference on Principles and Practice of Constraint Programming (CP’09). Lisbon, Portugal

Hybridizing Integer Programming models with an adaptive decomposition approach for exam timetabling problems
He, F. 2009. Hybridizing Integer Programming models with an adaptive decomposition approach for exam timetabling problems. 4th Multidisciplinary International Scheduling Conference (MISTA2009). Dublin 10 - 12 Aug 2009

A hybrid Constraint Programming approach for nurse rostering problems
He, F. 2008. A hybrid Constraint Programming approach for nurse rostering problems. AI-2008 Twenty-Eighth SGAI International Conference on Artificial Intelligence. Cambridge 09 - 11 Dec 2008

Permalink - https://westminsterresearch.westminster.ac.uk/item/9w1y7/a-constraint-programming-based-column-generation-approach-to-nurse-rostering-problems


Share this
Tweet
Email