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