Nurse Rostering Problem

This page provides supplementary material related to the research published in the paper:

Abstract: This work presents Integer Programming (IP) techniques to tackle the problem of the International Nurse Rostering Competition. Starting from a compact and monolithic formulation in which the current generation of solvers performs poorly, improved cut generation strategies and primal heuristics are proposed and evaluated. A large number of computational experiments with these techniques produced the following results: the optimality of the vast majority of instances was proved, the best known solutions were improved by up to 15% and strong dual bounds were obtained. In the spirit of reproducible science, all code was implemented using the Computational Infrastructure for Operations Research (COIN-OR).

Keywords: Nurse Rostering - Integer Programming - Cutting Planes - MIP Heuristics

Downloads

Use the links below to download instances, solutions and source code:

Instance information

Click here for legend of abbreviations.

The table below includes instance information and best known lower and upper bounds (including solutions obtained by other approaches).

Name Const Bin Int Nod Cliq Rnbc Rnac LB UB Gap Time Obj 1-3 4 5.1 5.2 6 7 8 9 10 11 12 13
Easy long_early01 14742 52332 98 1219 361 181.00 197.00 197.00 197.00 0.00 91.57 197
Easy long_early02 14742 52332 98 1892 623 191.93 216.28 219.00 219.00 0.00 209.90 219
Easy long_early03 14742 52332 98 0 286 223.50 239.50 240.00 240.00 0.00 23.94 240
Easy long_early04 14742 52346 84 0 402 288.00 303.00 303.00 303.00 0.00 25.47 303
Easy long_early05 14742 52332 98 0 378 269.00 284.00 284.00 284.00 0.00 41.69 284
Hard long_hidden01 24275 63435 100 26985 988 246.00 319.00 341.00 346.00 1.40 288.10 346
Hard long_hidden02 24275 63435 100 12241 795 74.83 81.00 86.00 89.00 3.40 14435.61 89
Hard long_hidden03 24680 64240 100 6405 1063 10.00 17.00 35.30 38.00 7.10 14421.09 38
Hard long_hidden04 24275 63435 100 7518 1089 12.50 13.67 19.00 22.00 13.80 14424.27 22
Medium long_hidden05 23840 62600 100 5990 844 31.00 39.09 41.00 41.00 0.00 5984.67 41
Hard long_late01 24065 63025 100 5694 746 138.79 205.08 232.00 235.00 1.30 5944.71 235
Medium long_late02 24041 63001 100 2608 634 147.50 207.33 229.00 229.00 0.00 4519.64 229
Hard long_late03 24065 63025 100 229588 591 141.75 213.36 219.00 220.00 0.50 14408.83 220
Hard long_late04 24041 63001 100 28879 770 152.27 197.50 214.63 222.00 3.30 14428.12 221
Medium long_late05 23707 62347 100 5073 1090 72.00 79.50 83.00 83.00 0.00 11061.00 83
Easy medium_early01 7211 29977 62 0 293 240.00 240.00 240.00 240.00 0.00 31.41 240
Easy medium_early02 7211 29977 62 0 440 235.00 239.12 240.00 240.00 0.00 31.74 240
Easy medium_early03 7211 29977 62 0 399 232.00 235.50 236.00 236.00 0.00 30.70 236
Easy medium_early04 7211 29985 54 18 446 233.00 236.12 237.00 237.00 0.00 36.08 237
Easy medium_early05 7211 29977 62 0 558 278.25 302.07 303.00 303.00 0.00 34.53 303
Hard medium_hidden01 14160 37120 60 21354 500 0.00 63.34 87.15 111.00 21.50 14410.76 111
Hard medium_hidden02 14160 37120 60 46000 468 111.00 180.18 196.64 221.00 11.10 14413.83 221
Hard medium_hidden03 14160 37120 60 16570 523 0.00 22.18 27.70 34.00 18.50 14404.20 34
Hard medium_hidden04 14160 37120 60 25802 498 31.00 57.48 72.80 78.00 6.70 14412.47 78
Hard medium_hidden05 14160 37120 60 21552 457 56.00 56.00 90.83 119.00 23.67 14410.40 119
Hard medium_late01 12412 34440 60 57272 725 64.34 143.00 155.70 157.00 0.80 3704.54 157
Easy medium_late02 12336 34364 60 571 230 6.38 17.42 18.00 18.00 0.00 177.32 18
Easy medium_late03 7206 29234 60 3744 460 9.41 25.66 29.00 29.00 0.00 353.37 29
Easy medium_late04 12292 34240 60 1565 562 5.69 31.29 35.00 35.00 0.00 725.62 35
Easy medium_late05 12560 35520 60 10475 573 30.01 96.52 107.00 107.00 0.00 1017.89 107
Easy sprint_early01 3052 10320 20 60 84 52.42 55.67 56.00 56.00 0.00 6.17 56
Easy sprint_early02 3052 10320 20 0 134 54.42 58.00 58.00 58.00 0.00 5.53 58
Easy sprint_early03 3052 10320 20 0 77 49.00 51.00 51.00 51.00 0.00 3.09 51
Easy sprint_early04 3052 10322 18 0 113 55.50 58.17 59.00 59.00 0.00 5.12 59
Easy sprint_early05 3052 10320 20 885 95 53.00 56.52 58.00 58.00 0.00 9.95 58
Easy sprint_early06 3052 10320 20 0 111 51.00 54.00 54.00 54.00 0.00 4.88 54
Easy sprint_early07 3052 10320 20 0 69 54.00 56.00 56.00 56.00 0.00 4.15 56
Easy sprint_early08 3052 10320 20 0 105 51.00 55.75 56.00 56.00 0.00 5.88 56
Easy sprint_early09 3052 10320 20 0 53 53.00 55.00 55.00 55.00 0.00 4.01 55
Easy sprint_early10 3052 10320 20 0 103 48.50 52.00 52.00 52.00 0.00 6.59 52
Easy sprint_hidden01 3332 10308 20 528 173 20.01 30.72 32.00 32.00 0.00 21.87 32
Easy sprint_hidden02 3304 10280 20 0 98 21.18 31.47 32.00 32.00 0.00 9.37 32
Easy sprint_hidden03 4442 11710 20 0 131 53.90 62.00 62.00 62.00 0.00 13.17 62
Easy sprint_hidden04 3810 10930 20 5 66 54.33 66.00 66.00 66.00 0.00 13.34 66
Easy sprint_hidden05 4474 11742 20 0 99 52.08 59.00 59.00 59.00 0.00 12.82 59
Easy sprint_hidden06 3285 10240 41 92 102 100.84 127.32 130.00 130.00 0.00 6.67 130
Easy sprint_hidden07 3294 10249 41 0 153 119.25 153.00 153.00 153.00 0.00 8.98 153
Easy sprint_hidden08 4432 11685 35 15 61 178.34 203.57 204.00 204.00 0.00 10.44 204
Easy sprint_hidden09 3785 10905 20 373 118 281.90 337.33 338.00 338.00 0.00 13.46 338
Easy sprint_hidden10 4429 11670 47 0 46 284.18 304.38 306.00 306.00 0.00 5.62 306
Easy sprint_late01 4447 11715 20 15 134 29.94 36.92 37.00 37.00 0.00 15.64 37
Easy sprint_late02 3259 10235 20 0 142 35.50 41.12 42.00 42.00 0.00 9.70 42
Easy sprint_late03 4447 11715 20 353 127 40.13 47.38 48.00 48.00 0.00 17.62 48
Easy sprint_late04 4467 11735 20 1075 150 52.96 69.65 73.00 73.00 0.00 33.00 73
Easy sprint_late05 4450 11718 20 721 112 38.50 43.38 44.00 44.00 0.00 18.54 44
Easy sprint_late06 2450 9718 20 0 100 38.00 41.50 42.00 42.00 0.00 6.98 42
Easy sprint_late07 2461 9729 20 0 106 36.00 41.59 42.00 42.00 0.00 7.98 42
Easy sprint_late08 2461 9729 20 794 258 9.50 15.00 17.00 17.00 0.00 35.21 17
Easy sprint_late09 2492 9792 20 860 187 9.50 13.50 17.00 17.00 0.00 32.20 17
Easy sprint_late10 2467 9735 20 0 130 34.89 42.41 43.00 43.00 0.00 8.38 43

Problem Status

Easy Easy - instance can be solved within one hour using a commercial solver
Medium Hard - instance has been solved, but is not considered easy
Hard Open - optimal solution to instance is unknown

Constraint Type Legend

1 minimum/maximum number of shifts assigned to a nurse
2 minimum/maximum number of consecutive free days
3 minimum/maximum number of consecutive working days
4 maximum number of working weekends in four weeks
5.1 maximum number of consecutive working weekends
5.2 minimum number of consecutive working weekends
6 number of days off after a series of night shifts
7 complete weekends
8 no night shift before free weekend
9 identical shift types during the weekend
10 alternative skill
11 unwanted patterns
12 day on/off request
13 shift on/off request

GOAL - Group of Optimization and Algorithms
Department of Computing  |  Federal University of Ouro Preto
Campus Morro do Cruzeiro  |  35400-000  |  Ouro Preto - MG, Brazil
Phone: +55 31 3559-1692  |  toffolo[ at ]iceb.ufop.br