Benchmarks

2021-02-04
12 min read

The following tables show the summary of the evaluation results compared with Gurobi9.01 and Cplex12.9.

All project files and related mps/lp files can be found on the Github.

Classical Benchmarks

Time is the best arrival time, not exact solution time.

Weeks Employees Cplex Value Gurobi Value Schedule Nurse ⅢValue Cplex Time(sec) Gurobi Time(sec) Schedule Nurse Ⅲ (sec)
Millar-2Shift-DATA1.1 2 8 0 0 0 0.41 0.4 0.167
Millar-2Shift-DATA1 2 8 0 0 0 0.4 0.25 0.174
SINTEF 3 24 0 0 0 3.57 3.48 4
Ozkarahan 1 14 0 0 0 0.03 0.02 0.13
Musa 2 11 175 175 175 0.01 0.02 10
Gpost-B 4 8 3 3 3 351 83 7.75
Gpost 4 8 5 5 5 206 29.93 7
LLR 1 27 301 301 301 5.04 5.77 4
Azaiez 4 13 0 0 0 9 2.93 6
BCDT-Sep 4 20 170 150 100 23138 965
BCV-4.13.1 4 13 10 10 10 5.17 0.78 14.35
QMC-1 4 19 13 13 13 5.2 3.62 8
WHPP 2 30 1001 1001 5 6314 9874 21
Valouxis-1 4 16 20 20 20 900 282 11.5
ikegami-2Shift-DATA1 4 28 0 0 0 20.22 4.91 5
ikegami-3Shift-DATA1 4 25 2 2 2 1630 170 9.4
ikegami-3Shift-DATA1.1 4 25 3 3 3 378 11
ikegami-3Shift-DATA1.2 4 25 3 3 3 425 11.3

References

  1. Asta, S., Özcan, E., and Curtois, T. A tensor based hyper-heuristic for nurse rostering. Knowledge-based systems, 2016. 98: p. 185-199.

  2. Burke E.K. and T. Curtois. New Approaches to Nurse Rostering Benchmark Instances. European Journal of Operational Research, 2014. 237(1): p. 71-81. pdf.

  3. Solos, Ioannis P., Ioannis X. Tassopoulos and Grigorios N. Beligiannis. A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem. Algorithms, 2013. 6: p. 278-308.

First Nurse Scheduling Competition 2010

Cplex 12.9 NEOS 8h timeout

Weeks Employees LB UB Exact Solution Time(sec)
sprint_early_01 4 10 56 56 1.59
sprint_early_02 4 10 58 58 1.93
sprint_early_03 4 10 51 51 1.43
sprint_early_04 4 10 59 59 1.78
sprint_early_05 4 10 58 58 3.52
sprint_early_06 4 10 54 54 1.83
sprint_early_07 4 10 56 56 1.06
sprint_early_08 4 10 56 56 0.83
sprint_early_09 4 10 55 55 0.59
sprint_early_10 4 10 52 52 0.84
sprint_hidden_01 4 10 32 32 64.04
sprint_hidden_02 4 10 32 32 4.49
sprint_hidden_03 4 10 62 62 10.87
sprint_hidden_04 4 10 66 66 75
sprint_hidden_05 4 10 59 59 17.34
sprint_hidden_06 4 10 130 130 9.51
sprint_hidden_07 4 10 153 153 4.45
sprint_hidden_08 4 10 204 204 9.79
sprint_hidden_09 4 10 338 338 65.33
sprint_hidden_10 4 10 306 306 9.01
sprint_late_01 4 10 37 37 10.01
sprint_late_02 4 10 42 42 4.2
sprint_late_03 4 10 48 48 8.62
sprint_late_04 4 10 73 73 84.96
sprint_late_05 4 10 44 44 8.22
sprint_late_06 4 10 42 42 4.87
sprint_late_07 4 10 42 42 10.18
sprint_late_08 4 10 17 17 98.17
sprint_late_09 4 10 17 17 213
sprint_late_10 4 10 43 43 10.68
medium_early_01 4 31 240 240 37.3
medium_early_02 4 31 240 240 21.26
medium_early_03 4 31 236 236 22.54
medium_early_04 4 31 237 237 34.88
medium_early_05 4 31 303 303 71.86
medium_late_01 4 30 148 157
medium_late_02 4 30 18 18 761
medium_late_03 4 30 24 30
medium_late_04 4 30 33 35
medium_late_05 4 30 101 108
medium_hidden_01 4 30 37 119
medium_hidden_02 4 30 113 219
medium_hidden_03 4 30 35
medium_hidden_04 4 30 32 80
medium_hidden_05 4 30 58 119
long_early_01 4 49 197 197 13.05
long_early_02 4 49 219 219 48.9
long_early_03 4 49 240 240 9.73
long_early_04 4 49 303 303 20.5
long_early_05 4 49 284 284 22.95
long_late_01 4 50 88 238
long_late_02 4 50 88 233
long_late_03 4 50 73 232
long_late_04 4 50 191 222
long_late_05 4 50 72 83
long_hidden_01 4 50 377 435
long_hidden_02 4 50 86 94
long_hidden_03 4 50 9 47
long_hidden_04 4 50 13 22
long_hidden_05 4 50 31 42

References

  1. http://www.goal.ufop.br/nrp/

Gurobi 9.01 NEOS 8h timeout

Weeks Employees LB UB Exact Solution Time(sec)
sprint_early_01 4 10 56 56 0.68
sprint_early_02 4 10 58 58 0.79
sprint_early_03 4 10 51 51 0.69
sprint_early_04 4 10 59 59 1.11
sprint_early_05 4 10 58 58 1.14
sprint_early_06 4 10 54 54 0.54
sprint_early_07 4 10 56 56 0.67
sprint_early_08 4 10 56 56 1.02
sprint_early_09 4 10 55 55 0.64
sprint_early_10 4 10 52 52 1.03
sprint_hidden_01 4 10 32 32 37.69
sprint_hidden_02 4 10 32 32 7.22
sprint_hidden_03 4 10 62 62 4.72
sprint_hidden_04 4 10 66 66 32.3
sprint_hidden_05 4 10 59 59 86.36
sprint_hidden_06 4 10 130 130 7.23
sprint_hidden_07 4 10 153 153 4.41
sprint_hidden_08 4 10 204 204 37.5
sprint_hidden_09 4 10 338 338 27.8
sprint_hidden_10 4 10 306 306 5.17
sprint_late_01 4 10 37 37 11.63
sprint_late_02 4 10 42 42 6.17
sprint_late_03 4 10 48 48 7.93
sprint_late_04 4 10 73 73 40.04
sprint_late_05 4 10 44 44 4.45
sprint_late_06 4 10 42 42 1.6
sprint_late_07 4 10 42 42 3.87
sprint_late_08 4 10 17 17 10.94
sprint_late_09 4 10 17 17 12.84
sprint_late_10 4 10 43 43 3.38
medium_early_01 4 31 240 240 6.22
medium_early_02 4 31 240 240 13.65
medium_early_03 4 31 236 236 6.08
medium_early_04 4 31 237 237 15.3
medium_early_05 4 31 303 303 47.42
medium_late_01 4 30 157 157 3103
medium_late_02 4 30 18 18 285
medium_late_03 4 30 29 29 2902
medium_late_04 4 30 35 35 889
medium_late_05 4 30 107 107 827
medium_hidden_01 4 30 53 116
medium_hidden_02 4 30 195 220
medium_hidden_03 4 30 17 35
medium_hidden_04 4 30 53 83
medium_hidden_05 4 30 73 122
long_early_01 4 49 197 197 3.67
long_early_02 4 49 219 219 40.6
long_early_03 4 49 240 240 3.17
long_early_04 4 49 303 303 6.55
long_early_05 4 49 284 284 4.74
long_late_01 4 50 235 235 7471
long_late_02 4 50 229 229 4686
long_late_03 4 50 220 220 18139
long_late_04 4 50 221 221 14865
long_late_05 4 50
long_hidden_01 4 50 343 346
long_hidden_02 4 50 88 89
long_hidden_03 4 50 30 38
long_hidden_04 4 50 22 22 16032
long_hidden_05 4 50 41 41 15747

Scehdule Nurse Ⅲ

Weeks Employees LB UB Exact Solution Time(sec)
sprint_early_01 4 10 56 56 3.56
sprint_early_02 4 10 58 58 4.1
sprint_early_03 4 10 51 51 3.46
sprint_early_04 4 10 59 59 3.94
sprint_early_05 4 10 58 58 38
sprint_early_06 4 10 54 54 3.8
sprint_early_07 4 10 56 56 3.43
sprint_early_08 4 10 56 56 6.57
sprint_early_09 4 10 55 55 3.78
sprint_early_10 4 10 52 52 3.46
sprint_hidden_01 4 10 32 32 3.89
sprint_hidden_02 4 10 32 32 3
sprint_hidden_03 4 10 62 62 3.96
sprint_hidden_04 4 10 66 66 11.17
sprint_hidden_05 4 10 59 59 6.7
sprint_hidden_06 4 10 130 130 4.15
sprint_hidden_07 4 10 153 153 3.85
sprint_hidden_08 4 10 204 204 6.9
sprint_hidden_09 4 10 338 338 9.6
sprint_hidden_10 4 10 306 306 8.4
sprint_late_01 4 10 37 37 5.1
sprint_late_02 4 10 42 42 4.3
sprint_late_03 4 10 48 48 7.3
sprint_late_04 4 10 73 73 7.14
sprint_late_05 4 10 44 44 43
sprint_late_06 4 10 42 42 6.2
sprint_late_07 4 10 42 42 9.5
sprint_late_08 4 10 17 17 6.1
sprint_late_09 4 10 17 17 5.6
sprint_late_10 4 10 43 43 4.75
medium_early_01 4 31 240 240 74
medium_early_02 4 31 240 240 26
medium_early_03 4 31 236 236 98
medium_early_04 4 31 237 237 35
medium_early_05 4 31 303 303 186
medium_late_01 4 30 157 157 154
medium_late_02 4 30 18 18 13
medium_late_03 4 30 29 29 103
medium_late_04 4 30 35 35 16.9
medium_late_05 4 30 107 107 38
medium_hidden_01 4 30 106 111 28800
medium_hidden_02 4 30 213 219 28800
medium_hidden_03 4 30 34 34 310
medium_hidden_04 4 30 76 78 28800
medium_hidden_05 4 30 118 118 751
long_early_01 4 49 197 197 74.5
long_early_02 4 49 219 219 230
long_early_03 4 49 240 240 59
long_early_04 4 49 303 303 113
long_early_05 4 49 284 284 179
long_late_01 4 50 235 235 374
long_late_02 4 50 229 229 319
long_late_03 4 50 219 220 28800
long_late_04 4 50 221 221 409
long_late_05 4 50 83 83 300
long_hidden_01 4 50 346 346 380
long_hidden_02 4 50 89 89 384
long_hidden_03 4 50 38 38 419
long_hidden_04 4 50 22 22 92
long_hidden_05 4 50 41 41 61

Nurse Rostering Benchmark Instances

Cplex 12.9 NEOS 8h timeout

Instance Name Weeks Employees LB UB Exact Solution Time(sec)
instance1 2 8 607 607 0.19
instance2 2 14 828 828 0.64
instance3 2 20 1001 1001 1.54
instance4 4 10 1716 1716 6.76
instance5 4 16 1143 1143 20.85
instance6 4 18 1950 1950 10.27
instance7 4 20 1056 1056 55.84
instance8 4 30 1300 1300 2423
instance9 4 36 memory out 439
instance10 4 40 4631 4631 57.45
instance11 4 50 3443 3443 27.1
instance12 4 60 4040 4040 549
instance13 4 120
instance14 6 32 1278 1278 3928
instance15 6 45 memory out 4313
instance16 8 20 3225 3225 2939
instance17 8 32 5746 5746 6852
instance18 12 22 4459 4459 13121
instance19 12 40 3145.7 3157
instance20 26 50 Not feasible

Gurobi 9.01 NEOS 8h timeout

Instance Name Weeks Employees LB UB Exact Solution Time(sec)
instance1 2 8 607 607 0.36
instance2 2 14 828 828 0.63
instance3 2 20 1001 1001 1.55
instance4 4 10 1716 1716 16.64
instance5 4 16 1143 1143 42.73
instance6 4 18 1950 1950 11.52
instance7 4 20 1056 1056 30.57
instance8 4 30 1300 1300 3445
instance9 4 36 406 439
instance10 4 40 4631 4631 90.06
instance11 4 50 3443 3443 93.43
instance12 4 60 4040 4040 243
instance13 4 120
instance14 6 32 1278 1278 378
instance15 6 45 3826 3836
instance16 8 20 3225 3225 76.7
instance17 8 32 5746 5746 173
instance18 12 22 4459 4459 1351
instance19 12 40 3149 3149 4101
instance20 26 50 4769 4769 6371

Scehdule Nurse Ⅲ

Instance Name Weeks Employees LB UB Exact Solution Time(sec)
instance1 2 8 607 607 3
instance2 2 14 828 828 1.76
instance3 2 20 1001 1001 2.81
instance4 4 10 1716 1716 1.59
instance5 4 16 1143 1143 7.89
instance6 4 18 1950 1950 4.17
instance7 4 20 1056 1056 16
instance8 4 30 1300 1300 217
instance9 4 36 406 439 28800
instance10 4 40 4631 4631 51.8
instance11 4 50 3443 3443 47
instance12 4 60 4040 4040 489
instance13 4 120
instance14 6 32 1278 1278 30
instance15 6 45 3829 3832 19564
instance16 8 20 3225 3225 33
instance17 8 32 5746 5746 28
instance18 12 22 4419 4466 28800
instance19 12 40 3148 3150 28800
instance20 26 50 4769 4769 23500

References

  1. Strandmark, P., Qu, Y. and Curtois, T. First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem. Computers & Operations Research, 2020. 120, p. 104945. (pdf)
  2. Demirović, E., Musliu, N., and Winter, F. Modeling and solving staff scheduling with partial weighted maxSAT. Annals of Operations Research, 2019. 275(1): p. 79-99.
  3. Smet P. Constraint reformulation for nurse rostering problems, in: PATAT 2018 twelfth international conference on the practice and theory of automated timetabling, Vienna, August, 2018, p. 69-80.
  4. Rahimian, E., Akartunalı, K., and Levine, J. A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems. European Journal of Operational Research, 2017. 258(2): p. 411-423.

Second Nurse Scheduling Competition

4Weeks

So far Best Known

Instance Weeks Employees LB UB GAP
n030w4 1 6-2-9-1 4 30 1615 1685 4.33%
n030w4 1 6-7-5-3 4 30 1740 1840 5.75%
n035w4 0 1-7-1-8 4 35 1250 1415 13.20%
n035w4 2 8-8-7-5 4 35 1045 1145 9.57%
n040w4 0 2-0-6-1 4 40 1335 1640 22.85%
n040w4 2 6-1-0-6 4 40 1570 1865 18.79%
n050w4 0 0-4-8-7 4 50 1195 1445 20.92%
n050w4 0 7-2-7-2 4 50 1200 1405 17.08%
n060w4 1 6-1-1-5 4 60 2380 2465 3.57%
n060w4 1 9-6-3-8 4 60 2615 2730 4.40%
n070w4 0 3-6-5-1 4 70 2280 2430 6.58%
n070w4 0 4-9-6-7 4 70 1990 2125 6.78%
n080w4 2 4-3-3-3 4 80 3140 3320 5.73%
n080w4 2 6-0-4-8 4 80 3045 3240 6.40%
n100w4 0 1-1-0-8 4 100 1055 1230 16.59%
n100w4 2 0-6-4-6 4 100 1470 1855 26.19%
n110w4 0 1-4-2-8 4 110 2210 2390 8.14%
n110w4 0 1-9-3-5 4 110 2255 2525 11.97%
n120w4 1 4-6-2-6 4 120 1790 2165 20.95%
n120w4 1 5-6-9-8 4 120 1820 2220 21.98%

Schedule Nurse Ⅲ

Instance Weeks Employees LB UB GAP
n030w4 1 6-2-9-1 4 30 1670 1670 0.00%
n030w4 1 6-7-5-3 4 30 1815 1815 0.00%
n035w4 0 1-7-1-8 4 35 1360 1360 0.00%
n035w4 2 8-8-7-5 4 35 1080 1080 0.00%
n040w4 0 2-0-6-1 4 40 1536 1565 1.89%
n040w4 2 6-1-0-6 4 40 1750 1750 0.00%
n050w4 0 0-4-8-7 4 50 1296 1320 1.85%
n050w4 0 7-2-7-2 4 50 1303 1315 0.92%
n060w4 1 6-1-1-5 4 60 2455 2455 0.00%
n060w4 1 9-6-3-8 4 60 2675 2675 0.00%
n070w4 0 3-6-5-1 4 70 2371 2380 0.38%
n070w4 0 4-9-6-7 4 70 2105 2115 0.48%
n080w4 2 4-3-3-3 4 80 3292 3300 0.24%
n080w4 2 6-0-4-8 4 80 3178 3190 0.38%
n100w4 0 1-1-0-8 4 100 1170 1170 0.00%
n100w4 2 0-6-4-6 4 100 1790 1790 0.00%
n110w4 0 1-4-2-8 4 110 2322 2330 0.34%
n110w4 0 1-9-3-5 4 110 2455 2455 0.00%
n120w4 1 4-6-2-6 4 120 2020 2020 0.00%
n120w4 1 5-6-9-8 4 120 2050 2050 0.00%

Gurobi 9.01(NEOS 8hours)

Instance Weeks Employees LB UB GAP
n030w4 1 6-2-9-1 4 30 1670 #VALUE!
n030w4 1 6-7-5-3 4 30 1772 1840 3.84%
n035w4 0 1-7-1-8 4 35 1122 1435 27.90%
n035w4 2 8-8-7-5 4 35 841 1165 38.53%
n040w4 0 2-0-6-1 4 40 1298 1610 24.04%
n040w4 2 6-1-0-6 4 40 1545 1790 15.86%
n050w4 0 0-4-8-7 4 50 #VALUE!
n050w4 0 7-2-7-2 4 50 1070 1410 31.78%
n060w4 1 6-1-1-5 4 60 1980 2995 51.26%
n060w4 1 9-6-3-8 4 60 2099 3090 47.21%
n070w4 0 3-6-5-1 4 70 1980 2995 51.26%
n070w4 0 4-9-6-7 4 70 1342 2850 112.37%
n080w4 2 4-3-3-3 4 80 2627 3695 40.65%
n080w4 2 6-0-4-8 4 80 2679 3495 30.46%
n100w4 0 1-1-0-8 4 100 805 1210 50.31%
n100w4 2 0-6-4-6 4 100 1156 2315 100.26%
n110w4 0 1-4-2-8 4 110 2013 2380 18.23%
n110w4 0 1-9-3-5 4 110 2049 2500 22.01%
n120w4 1 4-6-2-6 4 120 1376 3320 141.28%
n120w4 1 5-6-9-8 4 120 1473 2765 87.71%
Next Conflict Analysis