A hybrid integer and constraint programming approach to solve nurse rostering problems

Erfan Rahimian, Kerem Akartunali, John Levine

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)
44 Downloads (Pure)


The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.
Original languageEnglish
Pages (from-to)83-94
Number of pages12
JournalComputers & Operations Research
Early online date27 Jan 2017
Publication statusE-pub ahead of print - 27 Jan 2017


  • timetabling
  • nurse rostering
  • hybrid algorithm
  • integer programming
  • constraint programming


Dive into the research topics of 'A hybrid integer and constraint programming approach to solve nurse rostering problems'. Together they form a unique fingerprint.

Cite this