Dantzig-Wolfe Decomposition applied files(MPS files) by schedule nurse3
are here(zip archived).
So Far Best Known Result | Scedule Nurse 3 Result | |||||||
Instance | Weeks | Employees | Shift types | Best known lower bound | Best known solution | Lower Bound | Solution | Master LP File(MPS) |
Instance1 | 2 | 8 | 1 | 607 | 607 | 607 | 607 | master_lp_instance1.mps |
Instance2 | 2 | 14 | 2 | 828 | 828 | 828 | 828 | master_lp_instance2.mps |
Instance3 | 2 | 20 | 3 | 1001 | 1001 | 1001 | 1001 | master_lp_instance3.mps |
Instance4 | 4 | 10 | 2 | 1716 | 1716 | 1716 | 1716 | master_lp_instance4.mps |
Instance5 | 4 | 16 | 2 | 1143 | 1143 | 1143 | 1143 | master_lp_instance5.mps |
Instance6 | 4 | 18 | 3 | 1950 | 1950 | 1950 | 1950 | master_lp_instance6.mps |
Instance7 | 4 | 20 | 3 | 1056 | 1056 | 1056 | 1056 | master_lp_instance7.mps |
Instance8 | 4 | 30 | 4 | 1300 | 1300 | 1300 | 1300 | master_lp_instance8.mps |
Instance9 | 4 | 36 | 4 | 439 | 439 | 439 | 439 | master_lp_instance9.mps |
Instance10 | 4 | 40 | 5 | 4631 | 4631 | 4631 | 4631 | master_lp_instance10.mps |
Instance11 | 4 | 50 | 6 | 3443 | 3443 | 3443 | 3443 | master_lp_instance11.mps |
Instance12 | 4 | 60 | 10 | 4040 | 4040 | 4040 | 4040 | master_lp_instance12.mps |
Instance13 | 4 | 120 | 18 | 1348 | 1348 | |||
Instance14 | 6 | 32 | 4 | 1278 | 1278 | 1278 | 1278 | master_lp_instance14.mps |
Instance15 | 6 | 45 | 6 | 3823 | 3833 | 3827 | 3833 | master_lp_instance15.mps |
Instance16 | 8 | 20 | 3 | 3225 | 3225 | 3225 | 3225 | master_lp_instance16.mps |
Instance17 | 8 | 32 | 4 | 5746 | 5746 | 5746 | 5746 | master_lp_instance17.mps |
Instance18 | 12 | 22 | 3 | 4459 | 4459 | 4459 | 4459 | master_lp_instance18.mps |
Instance19 | 12 | 40 | 5 | 3149 | 3149 | master_lp_instance19.mps | ||
Instance20 | 26 | 50 | 6 | 4769 | 4769 | 4769 | 4769 | master_lp_instance20.mps |
Instance21 | 26 | 100 | 8 | 21124 | 21159 | |||
Instance22 | 52 | 50 | 10 | 28997 | 31279 | |||
Instance23 | 52 | 100 | 16 | 16990 | 17428 | |||
Instance24 | 52 | 150 | 32 | 26571 | 42463 |
INRC2 Result
4Weeks
So Far Best Known Result | Schedule Nurse 3 | |||||||
Instance | Weeks | Employees | Best known lower bound | Best known solution | Gap | lower bound | Solution | Gap |
n030w4 1 6-2-9-1 | 4 | 30 | 1615 | 1685 | 4.20% | 1660 | 1670 | 0.60% |
n030w4 1 6-7-5-3 | 4 | 30 | 1740 | 1840 | 5.40% | 1810 | 1815 | 0.30% |
n035w4 0 1-7-1-8 | 4 | 35 | 1250 | 1415 | 11.70% | 1338 | 1360 | 1.60% |
n035w4 2 8-8-7-5 | 4 | 35 | 1045 | 1145 | 8.70% | 1080 | 1080 | 0.00% |
n040w4 0 2-0-6-1 | 4 | 40 | 1335 | 1640 | 18.60% | 1536 | 1570 | 2.20% |
n040w4 2 6-1-0-6 | 4 | 40 | 1570 | 1865 | 15.80% | 1742 | 1750 | 0.50% |
n050w4 0 0-4-8-7 | 4 | 50 | 1195 | 1445 | 17.30% | 1296 | 1320 | 1.80% |
n050w4 0 7-2-7-2 | 4 | 50 | 1200 | 1405 | 14.60% | 1303 | 1315 | 0.90% |
n060w4 1 6-1-1-5 | 4 | 60 | 2380 | 2465 | 3.40% | 2435 | 2450 | 0.60% |
n060w4 1 9-6-3-8 | 4 | 60 | 2615 | 2730 | 4.20% | 2665 | 2675 | 0.40% |
n070w4 0 3-6-5-1 | 4 | 70 | 2280 | 2430 | 6.20% | 2371 | 2380 | 0.40% |
n070w4 0 4-9-6-7 | 4 | 70 | 1990 | 2125 | 6.40% | 2105 | 2115 | 0.50% |
n080w4 2 4-3-3-3 | 4 | 80 | 3140 | 3320 | 5.40% | 3292 | 3300 | 0.20% |
n080w4 2 6-0-4-8 | 4 | 80 | 3045 | 3240 | 6.00% | 3178 | 3190 | 0.40% |
n100w4 0 1-1-0-8 | 4 | 100 | 1055 | 1230 | 14.20% | 1168 | 1175 | 0.60% |
n100w4 2 0-6-4-6 | 4 | 100 | 1470 | 1855 | 20.80% | 1790 | 1790 | 0.00% |
n110w4 0 1-4-2-8 | 4 | 110 | 2210 | 2390 | 7.50% | 2322 | 2330 | 0.30% |
n110w4 0 1-9-3-5 | 4 | 110 | 2255 | 2525 | 10.70% | 2455 | 2455 | 0.00% |
n120w4 1 4-6-2-6 | 4 | 120 | 1790 | 2165 | 17.30% | 2032 | 2040 | 0.40% |
n120w4 1 5-6-9-8 | 4 | 120 | 1820 | 2220 | 18.00% | 2050 | 2050 | 0.00% |
8Weeks
Known Best Result | New Result | |||||||
Instance | Weeks | Employees | Best known lower bound | Best known solution | Gap | lower bound | Solution | Gap |
n030w8 1 2-7-0-9-3-6-0-6 | 8 | 30 | 1920 | 2070 | 7.2 | 1994 | 2025 | 1.5 |
n030w8 1 6-7-5-3-5-6-2-9 | 8 | 30 | 1620 | 1735 | 6.6 | 1710 | 1735 | 1.4 |
n035w8 0 6-2-9-8-7-7-9-8 | 8 | 35 | 2330 | 2555 | 8.8 | 2408 | 2495 | 3.5 |
n035w8 1 0-8-1-6-1-7-2-0 | 8 | 35 | 2180 | 2305 | 5.4 | 2153 | 2290 | 6 |
n040w8 0 0-6-8-9-2-6-6-4 | 8 | 40 | 2340 | 2620 | 10.7 | 2464 | 2600 | 5.2 |
n040w8 2 5-0-4-8-7-1-7-2 | 8 | 40 | 2205 | 2420 | 8.9 | 2285 | 2345 | 2.6 |
n050w8 1 1-7-8-5-7-4-1-8 | 8 | 50 | 4625 | 4900 | 5.6 | 4778 | 4865 | 1.8 |
n050w8 1 9-7-5-3-8-8-3-1 | 8 | 50 | 4530 | 4925 | 8 | 4744 | 4870 | 2.6 |
n060w8 0 6-2-9-9-0-8-1-3 | 8 | 60 | 1970 | 2345 | 16 | 2099 | 2280 | 7.9 |
n060w8 2 1-0-3-4-0-3-9-1 | 8 | 60 | 2260 | 2590 | 12.7 | 2394 | 2485 | 3.7 |
n070w8 0 3-3-9-2-3-7-5-2 | 8 | 70 | 4400 | 4595 | 4.2 | 4475 | 4575 | 2.2 |
n070w8 0 9-3-0-7-2-1-1-0 | 8 | 70 | 4540 | 4760 | 4.6 | 4637 | 4755 | 2.5 |
n080w8 1 4-4-9-9-3-6-0-5 | 8 | 80 | 3775 | 4180 | 9.7 | 3942 | 4155 | 5.1 |
n080w8 2 0-4-0-9-1-9-6-2 | 8 | 80 | 4125 | 4450 | 7.3 | 4287 | 4385 | 2.2 |
n100w8 0 0-1-7-8-9-1-5-4 | 8 | 100 | 2005 | 2125 | 5.6 | 2026 | DUT | |
n100w8 1 2-4-7-9-3-9-2-8 | 8 | 100 | 2125 | 2210 | 3.8 | 2153 | 2185 | 1.5 |
n110w8 0 2-1-1-7-2-6-4-7 | 8 | 110 | 3870 | 4010 | 3.5 | 3990 | 3990 | 0 |
n110w8 0 3-2-4-9-4-1-3-7 | 8 | 110 | 3375 | 3560 | 5.2 | 3450 | 3450 | 0 |
n120w8 0 0-9-9-4-5-1-0-3 | 8 | 120 | 2295 | 2600 | 11.7 | 2485 | 2495 | 0.4 |
n120w8 1 7-2-6-4-5-2-0-2 | 8 | 120 | 2535 | 3095 | 18.1 | 2912 | 2930 | 0.6 |
Runtime(sec) Result of LP solvers for the files above.
Time | Ratio for CLP | ||||||||||||
File Size | Istance Name | Mark | CLP | HiGHs Simplex | HiGHs IPX | Copt1.4.3 Simplex | Copt1.4.3 Barrier(4Tthreads) | CLP | HiGHs Simplex | HiGHs IPX | Copt1.4.3 Simplex | Copt 1.43 Barrier(4Threads) | |
39655 | master_lp_instance1.mps | 0.002 | 0.00721 | 0.0149 | 0 | 0.01 | 1.0 | 3.6 | 7.5 | 0.0 | 5.0 | ||
106902 | master_lp_instance2.mps | 0.002 | 0.00974 | 0.0239 | 0 | 0.01 | 1.0 | 4.9 | 12.0 | 0.0 | 5.0 | ||
142564 | master_lp_instance3.mps | 0.032 | 0.0129 | 0.035 | 0.02 | 0.02 | 1.0 | 0.4 | 1.1 | 0.6 | 0.6 | ||
299143 | master_lp_instance4.mps | 0.032 | 0.023 | 0.0489 | 0.02 | 0.03 | 1.0 | 0.7 | 1.5 | 0.6 | 0.9 | ||
470198 | master_lp_instance5.mps | 0.052 | 0.0416 | 0.0664 | 0.06 | 0.05 | 1.0 | 0.8 | 1.3 | 1.2 | 1.0 | ||
611873 | master_lp_instance6.mps | 0.122 | 0.0852 | 0.103 | 0.09 | 0.08 | 1.0 | 0.7 | 0.8 | 0.7 | 0.7 | ||
716630 | master_lp_n005w4_1_6-2-9-1.mps | 0.112 | 0.0737 | 0.128 | 0.08 | 0.06 | 1.0 | 0.7 | 1.1 | 0.7 | 0.5 | ||
859250 | master_lp_instance9.mps | 0.192 | 0.169 | 0.177 | 0.18 | 0.09 | 1.0 | 0.9 | 0.9 | 0.9 | 0.5 | ||
890661 | master_lp_instance7.mps | 0.142 | 0.0961 | 0.136 | 0.15 | 0.1 | 1.0 | 0.7 | 1.0 | 1.1 | 0.7 | ||
1064753 | master_lp_instance10.mps | 0.272 | 0.258 | 0.201 | 0.31 | 0.15 | 1.0 | 0.9 | 0.7 | 1.1 | 0.6 | ||
1100634 | master_lp_instance11.mps | 0.172 | 0.191 | 0.219 | 0.28 | 0.22 | 1.0 | 1.1 | 1.3 | 1.6 | 1.3 | ||
1325528 | master_lp_instance8.mps | 0.202 | 0.191 | 0.237 | 0.23 | 0.18 | 1.0 | 0.9 | 1.2 | 1.1 | 0.9 | ||
1796572 | master_lp_instance16.mps | 0.302 | 0.243 | 0.272 | 0.31 | 0.3 | 1.0 | 0.8 | 0.9 | 1.0 | 1.0 | ||
2290140 | master_lp_n021w4_1_6-2-9-1.mps | * | 0.672 | 0.87 | 0.625 | 1.03 | 0.25 | 1.0 | 1.3 | 0.9 | 1.5 | 0.4 | |
2494894 | master_lp_instance14.mps | 0.422 | 0.561 | 0.451 | 0.62 | 0.4 | 1.0 | 1.3 | 1.1 | 1.5 | 0.9 | ||
2519526 | master_lp_n030w4_1_6-7-5-3.mps | 0.772 | 1.48 | 0.782 | 1.6 | 0.37 | 1.0 | 1.9 | 1.0 | 2.1 | 0.5 | ||
2616224 | master_lp_n030w4_1_6-2-9-1.mps | 0.702 | 1.32 | 0.799 | 1.38 | 0.35 | 1.0 | 1.9 | 1.1 | 2.0 | 0.5 | ||
2842788 | master_lp_n035w4_0_1-7-1-8.mps | 0.752 | 1.65 | 0.8 | 1.49 | 0.35 | 1.0 | 2.2 | 1.1 | 2.0 | 0.5 | ||
2852052 | master_lp_n035w4_2_8-8-7-5.mps | 0.662 | 1.49 | 0.787 | 1.2 | 0.38 | 1.0 | 2.3 | 1.2 | 1.8 | 0.6 | ||
2948572 | master_lp_n040w4_0_2-0-6-1.mps | * | 0.882 | 2.24 | 0.825 | 1.83 | 0.41 | 1.0 | 2.5 | 0.9 | 2.1 | 0.5 | |
2987744 | master_lp_instance17.mps | 0.552 | 0.486 | 0.451 | 0.65 | 0.52 | 1.0 | 0.9 | 0.8 | 1.2 | 0.9 | ||
2990077 | master_lp_n040w4_2_6-1-0-6.mps | 0.862 | 1.31 | 0.915 | 1.44 | 0.46 | 1.0 | 1.5 | 1.1 | 1.7 | 0.5 | ||
3132335 | master_lp_instance12.mps | * | 1.332 | 1.92 | 1.02 | 2.08 | 0.64 | 1.0 | 1.4 | 0.8 | 1.6 | 0.5 | |
3618932 | master_lp_n060w4_1_9-6-3-8.mps | 1.092 | 2.76 | 1.12 | 2.4 | 0.66 | 1.0 | 2.5 | 1.0 | 2.2 | 0.6 | ||
3823456 | master_lp_n060w4_1_6-1-1-5.mps | * | 1.282 | 5.98 | 1.23 | 4.25 | 0.68 | 1.0 | 4.7 | 1.0 | 3.3 | 0.5 | |
4038195 | master_lp_n050w4_0_0-4-8-7.mps | 0.942 | 3.22 | 1.17 | 3.34 | 0.59 | 1.0 | 3.4 | 1.2 | 3.5 | 0.6 | ||
4073770 | master_lp_n050w4_0_7-2-7-2.mps | 1.122 | 3.48 | 1.4 | 3.41 | 0.86 | 1.0 | 3.1 | 1.2 | 3.0 | 0.8 | ||
4408051 | master_lp_instance15.mps | 0.942 | 1.86 | 1.06 | 1.8 | 0.85 | 1.0 | 2.0 | 1.1 | 1.9 | 0.9 | ||
4408614 | master_lp_n080w4_2_6-0-4-8.mps | * | 1.802 | 5.14 | 1.64 | 4.17 | 0.8 | 1.0 | 2.9 | 0.9 | 2.3 | 0.4 | |
4806029 | master_lp_n070w4_0_3-6-5-1.mps | 1.062 | 2.84 | 1.69 | 3.04 | 0.87 | 1.0 | 2.7 | 1.6 | 2.9 | 0.8 | ||
4822897 | master_lp_n080w4_2_4-3-3-3.mps | 1.702 | 3.41 | 1.92 | 3.39 | 0.91 | 1.0 | 2.0 | 1.1 | 2.0 | 0.5 | ||
5095952 | master_lp_n070w4_0_4-9-6-7.mps | 1.522 | 4.92 | 2.04 | 3.93 | 1.07 | 1.0 | 3.2 | 1.3 | 2.6 | 0.7 | ||
5318806 | master_lp_n100w4_2_0-6-4-6.mps | 1.582 | 6.1 | 2.07 | 4.35 | 0.94 | 1.0 | 3.9 | 1.3 | 2.7 | 0.6 | ||
5388648 | master_lp_n100w4_0_1-1-0-8.mps | 1.892 | 9.96 | 2.28 | 6.83 | 0.96 | 1.0 | 5.3 | 1.2 | 3.6 | 0.5 | ||
5601585 | master_lp_n110w4_0_1-4-2-8.mps | 1.752 | 7.26 | 2.51 | 6.35 | 1.23 | 1.0 | 4.1 | 1.4 | 3.6 | 0.7 | ||
5665876 | master_lp_n110w4_0_1-9-3-5.mps | 2.252 | 7.65 | 2.65 | 6.14 | 1.2 | 1.0 | 3.4 | 1.2 | 2.7 | 0.5 | ||
5755045 | master_lp_instance18.mps | 1.422 | 1.16 | 1.11 | 1.36 | 1.06 | 1.0 | 0.8 | 0.8 | 1.0 | 0.7 | ||
6380844 | master_lp_n012w8_1_2-7-0-9-3-6-0-6.mps | * | 2.582 | 5.25 | 2.38 | 5.92 | 1.14 | 1.0 | 2.0 | 0.9 | 2.3 | 0.4 | |
7322274 | master_lp_n120w4_1_4-6-2-6.mps | 16.202 | 13.1 | 3.2 | 8.7 | 1.44 | 1.0 | 0.8 | 0.2 | 0.5 | 0.1 | ||
7559874 | master_lp_n120w4_1_5-6-9-8.mps | 18.442 | 17.6 | 3.45 | 8.71 | 1.48 | 1.0 | 1.0 | 0.2 | 0.5 | 0.1 | ||
10094992 | master_lp_n030w8_1_2-7-0-9-3-6-0-6.mps | * | 5.522 | 11.6 | 5.4 | 13.06 | 2.4 | 1.0 | 2.1 | 1.0 | 2.4 | 0.4 | |
10128303 | master_lp_n030w8_1_6-7-5-3-5-6-2-9.mps | 5.392 | 11.8 | 5.49 | 14.07 | 2.4 | 1.0 | 2.2 | 1.0 | 2.6 | 0.4 | ||
10387644 | master_lp_n035w8_1_0-8-1-6-1-7-2-0.mps | * | 5.812 | 25 | 5.62 | 24.23 | 2.81 | 1.0 | 4.3 | 1.0 | 4.2 | 0.5 | |
10528340 | master_lp_n040w8_2_5-0-4-8-7-1-7-2.mps | * | 5.382 | 24.9 | 5.34 | 17.12 | 2.59 | 1.0 | 4.6 | 1.0 | 3.2 | 0.5 | |
10894198 | master_lp_n040w8_0_0-6-8-9-2-6-6-4.mps | * | 5.162 | 24.4 | 5.09 | 20.93 | 2.5 | 1.0 | 4.7 | 1.0 | 4.1 | 0.5 | |
10950628 | master_lp_n035w8_0_6-2-9-8-7-7-9-8.mps | * | 6.922 | 35.4 | 6.36 | 25.85 | 2.93 | 1.0 | 5.1 | 0.9 | 3.7 | 0.4 | |
15516919 | master_lp_n100w8_1_2-4-7-9-3-9-2-8.mps | * | 17.692 | 80.6 | 10.4 | 73.44 | 4.67 | 1.0 | 4.6 | 0.6 | 4.2 | 0.3 | |
15775024 | master_lp_n050w8_1_9-7-5-3-8-8-3-1.mps | 10.392 | 36.3 | 10.4 | 36.11 | 4.65 | 1.0 | 3.5 | 1.0 | 3.5 | 0.4 | ||
15860790 | master_lp_n050w8_1_1-7-8-5-7-4-1-8.mps | * | 11.422 | 39.6 | 11 | 41.73 | 4.98 | 1.0 | 3.5 | 1.0 | 3.7 | 0.4 | |
16039856 | master_lp_n100w8_0_0-1-7-8-9-1-5-4.mps | * | 19.562 | 103 | 12.5 | 68.59 | 5.35 | 1.0 | 5.3 | 0.6 | 3.5 | 0.3 | |
16361269 | master_lp_n110w8_0_3-2-4-9-4-1-3-7.mps | * | 19.772 | 59.4 | 13 | 57.44 | 5.5 | 1.0 | 3.0 | 0.7 | 2.9 | 0.3 | |
17062237 | master_lp_n070w8_0_9-3-0-7-2-1-1-0.mps | * | 22.482 | 243 | 16.4 | 133.76 | 6.85 | 1.0 | 10.8 | 0.7 | 5.9 | 0.3 | |
17147060 | master_lp_n110w8_0_2-1-1-7-2-6-4-7.mps | * | 50.252 | 96.1 | 14.4 | 84.99 | 5.65 | 1.0 | 1.9 | 0.3 | 1.7 | 0.1 | |
17250626 | master_lp_instance19.mps | 6.732 | 10.6 | 7.81 | 10.08 | 6.79 | 1.0 | 1.6 | 1.2 | 1.5 | 1.0 | ||
17262941 | master_lp_n070w8_0_3-3-9-2-3-7-5-2.mps | * | 25.022 | 104 | 15.9 | 68.11 | 6.79 | 1.0 | 4.2 | 0.6 | 2.7 | 0.3 | |
17343024 | master_lp_n060w8_2_1-0-3-4-0-3-9-1.mps | * | 17.842 | 82.8 | 12.1 | 59.29 | 5.08 | 1.0 | 4.6 | 0.7 | 3.3 | 0.3 | |
17346166 | master_lp_n080w8_1_4-4-9-9-3-6-0-5.mps | * | 23.442 | 178 | 15.1 | 79.28 | 6.06 | 1.0 | 7.6 | 0.6 | 3.4 | 0.3 | |
17670365 | master_lp_n080w8_2_0-4-0-9-1-9-6-2.mps | * | 24.592 | 115 | 13.6 | 75.51 | 5.77 | 1.0 | 4.7 | 0.6 | 3.1 | 0.2 | |
17715908 | master_lp_n060w8_0_6-2-9-9-0-8-1-3.mps | * | 18.172 | 122 | 11.8 | 81.16 | 4.73 | 1.0 | 6.7 | 0.6 | 4.5 | 0.3 | |
24423111 | master_lp_n120w8_0_0-9-9-4-5-1-0-3.mps | * | 39.972 | 156 | 23 | 116.64 | 8.76 | 1.0 | 3.9 | 0.6 | 2.9 | 0.2 | |
29218788 | master_lp_n120w8_1_7-2-6-4-5-2-0-2.mps | * | 57.192 | 688 | 36.6 | 181.063 | 15.79 | 1.0 | 12.0 | 0.6 | 3.2 | 0.3 | |
42502282 | master_lp_instance20.mps | * | 32.942 | 60.9 | 21.9 | 60.35 | 23.4 | 1.0 | 1.8 | 0.7 | 1.8 | 0.7 |
References:
Scheduling Benchmarks
INRC2 Data