| Unsplittable capacitated network design problem |
|
Results for C
Instances |
|
|
|
|
|
|
|
|
| Lowe Bound /
Upper Bound |
|
|
|
|
|
|
|
|
|
|
|
|
| Year |
|
2017 |
2017 |
2010 |
2012 |
2013 |
2013 |
2013 |
2013 |
2013 |
2018 |
2018 |
|
| Problem |
Problem |
Lower Bound 60h |
Upper Bound/ Gurobi/ 60h |
IP search |
Simulated Annealing |
Branch-and-Price Guided Search |
Branch-and-Price Guided Search+ |
Capacity Scaling and Restricted Branch-and-Bound
Matheuristic |
Capacity Scaling and Local Branch Matheuristic |
Capacity Scaling and Path Relinking Matheuristic |
Capacity Scaling and MIP Neighborhood Search |
Capacity Scaling and MIP Neighborhood Search Tuned |
|
| c33 |
20/230/040/V/L |
423933 |
423933 |
423933 |
|
424361 |
423933 |
424075 |
424075 |
423933 |
423933 |
423933 |
|
| c35 |
20/230/040/V/T |
398870 |
398870 |
398870 |
|
399810 |
398870 |
400380 |
400380 |
398870 |
398870 |
398870 |
|
| c36 |
20/230/040/F/T |
668699 |
668699 |
668699 |
670928 |
677331 |
668699 |
669642 |
669642 |
668699 |
668699 |
668699 |
|
| c37 |
20/230/200/V/L |
94644 |
94644 |
95695 |
118785 |
99669 |
94843 |
94644 |
94644 |
94644 |
95770 |
94765 |
|
| c38 |
20/230/200/F/L |
138084 |
138084 |
141700 |
|
145396 |
138476 |
138084 |
138084 |
138084 |
139394 |
138084 |
|
| c39 |
20/230/200/V/T |
98610 |
98610 |
100884 |
112792 |
101318 |
98947 |
98674 |
98610 |
98674 |
98754 |
98610 |
|
| c40 |
20/230/200/F/T |
135885 |
137499 |
141734 |
167006 |
146908 |
139889 |
137618 |
137594 |
137618 |
138517 |
137709 |
|
| c41 |
20/300/040/V/L |
430253 |
430253 |
430253 |
433929 |
432037 |
430314 |
430253 |
430253 |
430253 |
430253 |
430253 |
|
| c42 |
20/300/040/F/L |
597059 |
597059 |
597059 |
|
613908 |
597059 |
597170 |
597059 |
597059 |
597059 |
597059 |
|
| c43 |
20/300/040/V/T |
501766 |
501766 |
501766 |
511384 |
508653 |
501889 |
511019 |
511019 |
501766 |
501766 |
501766 |
|
| c44 |
20/300/040/F/T |
643395 |
643395 |
643395 |
656412 |
650686 |
643395 |
651667 |
644453 |
643395 |
643395 |
643395 |
|
| c45 |
20/300/200/V/L |
75070 |
75786 |
76946 |
91702 |
79215 |
76333 |
75820 |
75802 |
75820 |
75864 |
75864 |
|
| c46 |
20/300/200/F/L |
114409 |
117476 |
119590 |
151513 |
126944 |
118204 |
117814 |
117617 |
117814 |
118100 |
117570 |
|
| c47 |
20/300/200/V/T |
76281 |
76281 |
77055 |
88550 |
78773 |
76986 |
76549 |
76357 |
76483 |
76531 |
76357 |
|
| c48 |
20/300/200/F/T |
107192 |
109698 |
110516 |
|
116045 |
109776 |
109875 |
109385 |
109785 |
110302 |
109538 |
|
| c49 |
30/520/100/V/L |
54387 |
54387 |
54427 |
57422 |
57397 |
54387 |
54432 |
54387 |
54387 |
54387 |
54387 |
|
| c50 |
30/520/100/F/L |
95189 |
95877 |
97199 |
|
105045 |
96277 |
96357 |
95947 |
96134 |
96137 |
95877 |
|
| c51 |
30/520/100/V/T |
53812 |
53812 |
53812 |
|
56031 |
53812 |
53971 |
53961 |
53812 |
53812 |
53812 |
|
| c52 |
30/520/100/F/T |
99195 |
99195 |
100391 |
|
102923 |
99355 |
99355 |
99204 |
99204 |
99355 |
99204 |
|
| c53 |
30/520/400/V/L |
113038 |
114105 |
116465 |
134587 |
122604 |
114867 |
114405 |
114295 |
114405 |
114729 |
114355 |
|
| c54 |
30/520/400/F/L |
148308 |
150985 |
156433 |
|
175011 |
152837 |
150909 |
150965 |
150909 |
152654 |
151365 |
|
| c55 |
30/520/400/V/T |
115436 |
116306 |
118193 |
|
120213 |
116730 |
116318 |
116306 |
116318 |
116884 |
116428 |
|
| c56 |
30/520/400/F/T |
151207 |
155133 |
161513 |
|
176655 |
155982 |
155820 |
155720 |
155249 |
155913 |
155039 |
|
| c57 |
30/700/100/V/L |
47883 |
47883 |
47883 |
51505 |
51313 |
47883 |
47883 |
47883 |
47883 |
47883 |
47883 |
|
| c58 |
30/700/100/F/L |
60384 |
60384 |
61254 |
68179 |
63703 |
60384 |
60573 |
60384 |
60384 |
60829 |
60688 |
|
| c59 |
30/700/100/V/T |
47670 |
47670 |
47736 |
|
50740 |
47686 |
47766 |
47733 |
47670 |
47670 |
47670 |
|
| c60 |
30/700/100/F/T |
56686 |
56686 |
56931 |
|
59654 |
56809 |
56942 |
56934 |
56686 |
56898 |
56686 |
|
| c61 |
30/700/400/V/L |
97515.00789 |
98767 |
100368 |
|
106932 |
98850 |
98538 |
98535 |
98538 |
98689 |
98559 |
|
| c62 |
30/700/400/F/L |
131659 |
137004 |
144077 |
|
154019 |
138376 |
137468 |
137337 |
137017 |
138186 |
136812 |
|
| c63 |
30/700/400/V/T |
95128 |
96483 |
98040 |
|
103734 |
97352 |
96468 |
96475 |
96366 |
97260 |
96688 |
|
| c64 |
30/700/400/F/T |
128918 |
131692 |
135512 |
168070 |
148276 |
133759 |
132112 |
132112 |
132112 |
133307 |
132316 |
|
| Average |
193567 |
194465 |
196075 |
232184 |
201784 |
194934 |
195245 |
194940 |
194515 |
194897 |
194524 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Gaps(%) |
|
|
|
|
|
|
|
|
|
|
|
|
| c33 |
20/230/040/V/L |
|
0.00% |
0.00% |
|
0.10% |
0.00% |
0.03% |
0.03% |
0.00% |
0.00% |
0.00% |
|
| c35 |
20/230/040/V/T |
|
0.00% |
0.00% |
|
0.24% |
0.00% |
0.38% |
0.38% |
0.00% |
0.00% |
0.00% |
|
| c36 |
20/230/040/F/T |
|
0.00% |
0.00% |
0.33% |
1.29% |
0.00% |
0.14% |
0.14% |
0.00% |
0.00% |
0.00% |
|
| c37 |
20/230/200/V/L |
|
0.00% |
1.11% |
25.51% |
5.31% |
0.21% |
0.00% |
0.00% |
0.00% |
1.19% |
0.13% |
|
| c38 |
20/230/200/F/L |
|
0.00% |
2.62% |
|
5.30% |
0.28% |
0.00% |
0.00% |
0.00% |
0.95% |
0.00% |
|
| c39 |
20/230/200/V/T |
|
0.00% |
2.31% |
14.38% |
2.75% |
0.34% |
0.06% |
0.00% |
0.06% |
0.15% |
0.00% |
|
| c40 |
20/230/200/F/T |
|
1.19% |
4.30% |
22.90% |
8.11% |
2.95% |
1.28% |
1.26% |
1.28% |
1.94% |
1.34% |
|
| c41 |
20/300/040/V/L |
|
0.00% |
0.00% |
0.85% |
0.41% |
0.01% |
0.00% |
0.00% |
0.00% |
0.00% |
0.00% |
|
| c42 |
20/300/040/F/L |
|
0.00% |
0.00% |
|
2.82% |
0.00% |
0.02% |
0.00% |
0.00% |
0.00% |
0.00% |
|
| c43 |
20/300/040/V/T |
|
0.00% |
0.00% |
1.92% |
1.37% |
0.02% |
1.84% |
1.84% |
0.00% |
0.00% |
0.00% |
|
| c44 |
20/300/040/F/T |
|
0.00% |
0.00% |
2.02% |
1.13% |
0.00% |
1.29% |
0.16% |
0.00% |
0.00% |
0.00% |
|
| c45 |
20/300/200/V/L |
|
0.95% |
2.50% |
22.16% |
5.52% |
1.68% |
1.00% |
0.98% |
1.00% |
1.06% |
1.06% |
|
| c46 |
20/300/200/F/L |
|
2.68% |
4.53% |
32.43% |
10.96% |
3.32% |
2.98% |
2.80% |
2.98% |
3.23% |
2.76% |
|
| c47 |
20/300/200/V/T |
|
0.00% |
1.01% |
16.08% |
3.27% |
0.92% |
0.35% |
0.10% |
0.26% |
0.33% |
0.10% |
|
| c48 |
20/300/200/F/T |
|
2.34% |
3.10% |
|
8.26% |
2.41% |
2.50% |
2.05% |
2.42% |
2.90% |
2.19% |
|
| c49 |
30/520/100/V/L |
|
0.00% |
0.07% |
5.58% |
5.53% |
0.00% |
0.08% |
0.00% |
0.00% |
0.00% |
0.00% |
|
| c50 |
30/520/100/F/L |
|
0.72% |
2.11% |
|
10.35% |
1.14% |
1.23% |
0.80% |
0.99% |
1.00% |
0.72% |
|
| c51 |
30/520/100/V/T |
|
0.00% |
0.00% |
|
4.12% |
0.00% |
0.30% |
0.28% |
0.00% |
0.00% |
0.00% |
|
| c52 |
30/520/100/F/T |
|
0.00% |
1.21% |
|
3.76% |
0.16% |
0.16% |
0.01% |
0.01% |
0.16% |
0.01% |
|
| c53 |
30/520/400/V/L |
|
0.94% |
3.03% |
19.06% |
8.46% |
1.62% |
1.21% |
1.11% |
1.21% |
1.50% |
1.17% |
|
| c54 |
30/520/400/F/L |
|
1.81% |
5.48% |
|
18.01% |
3.05% |
1.75% |
1.79% |
1.75% |
2.93% |
2.06% |
|
| c55 |
30/520/400/V/T |
|
0.75% |
2.39% |
|
4.14% |
1.12% |
0.76% |
0.75% |
0.76% |
1.25% |
0.86% |
|
| c56 |
30/520/400/F/T |
|
2.60% |
6.82% |
|
16.83% |
3.16% |
3.05% |
2.98% |
2.67% |
3.11% |
2.53% |
|
| c57 |
30/700/100/V/L |
|
0.00% |
0.00% |
7.56% |
7.16% |
0.00% |
0.00% |
0.00% |
0.00% |
0.00% |
0.00% |
|
| c58 |
30/700/100/F/L |
|
0.00% |
1.44% |
12.91% |
5.50% |
0.00% |
0.31% |
0.00% |
0.00% |
0.74% |
0.50% |
|
| c59 |
30/700/100/V/T |
|
0.00% |
0.14% |
|
6.44% |
0.03% |
0.20% |
0.13% |
0.00% |
0.00% |
0.00% |
|
| c60 |
30/700/100/F/T |
|
0.00% |
0.43% |
|
5.24% |
0.22% |
0.45% |
0.44% |
0.00% |
0.37% |
0.00% |
|
| c61 |
30/700/400/V/L |
|
1.28% |
2.93% |
|
9.66% |
1.37% |
1.05% |
1.05% |
1.05% |
1.20% |
1.07% |
|
| c62 |
30/700/400/F/L |
|
4.06% |
9.43% |
|
16.98% |
5.10% |
4.41% |
4.31% |
4.07% |
4.96% |
3.91% |
|
| c63 |
30/700/400/V/T |
|
1.42% |
3.06% |
|
9.05% |
2.34% |
1.41% |
1.42% |
1.30% |
2.24% |
1.64% |
|
| c64 |
30/700/400/F/T |
|
2.15% |
5.11% |
30.37% |
15.02% |
3.76% |
2.48% |
2.48% |
2.48% |
3.40% |
2.64% |
|
| Average |
|
|
0.74% |
2.10% |
14.27% |
6.55% |
1.14% |
0.99% |
0.88% |
0.78% |
1.12% |
0.80% |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Computation
Time (seconds) |
|
|
|
|
|
|
|
|
|
|
|
|
| Problem |
Problem |
Lower Bound
60h |
Upper Bound/
Gurobi/ 60h |
IP search |
Simulated
Annealing |
Branch-and-Price
Guided Search |
Branch-and-Price
Guided Search+ |
Capacity
Scaling and Restricted Branch-and-Bound Matheuristic |
Capacity
Scaling and Local Branch Matheuristic |
Capacity
Scaling and Path Relinking Matheuristic |
Capacity
Scaling and MIP Neighborhood Search |
Capacity
Scaling and MIP Neighborhood Search Tuned |
|
| c33 |
20/230/040/V/L |
0 |
0 |
900 |
12000 |
1800 |
1800 |
0 |
2 |
3 |
1 |
1 |
|
| c35 |
20/230/040/V/T |
0 |
0 |
900 |
12000 |
1800 |
1800 |
2 |
2 |
3 |
1 |
1 |
|
| c36 |
20/230/040/F/T |
0 |
0 |
900 |
12000 |
1800 |
1800 |
2 |
2 |
4 |
1 |
1 |
|
| c37 |
20/230/200/V/L |
50338 |
50338 |
900 |
12000 |
1800 |
1800 |
6387 |
6230 |
12634 |
642 |
672 |
|
| c38 |
20/230/200/F/L |
101583 |
101583 |
900 |
12000 |
1800 |
1800 |
8444 |
7895 |
18309 |
537 |
555 |
|
| c39 |
20/230/200/V/T |
42202 |
42202 |
900 |
12000 |
1800 |
1800 |
7194 |
7318 |
13721 |
662 |
609 |
|
| c40 |
20/230/200/F/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
8406 |
8822 |
23225 |
729 |
731 |
|
| c41 |
20/300/040/V/L |
0 |
0 |
900 |
12000 |
1800 |
1800 |
0 |
2 |
3 |
1 |
1 |
|
| c42 |
20/300/040/F/L |
1 |
1 |
900 |
12000 |
1800 |
1800 |
1 |
3 |
6 |
3 |
2 |
|
| c43 |
20/300/040/V/T |
1 |
1 |
900 |
12000 |
1800 |
1800 |
1 |
1 |
3 |
1 |
1 |
|
| c44 |
20/300/040/F/T |
0 |
0 |
900 |
12000 |
1800 |
1800 |
1 |
3 |
3 |
1 |
1 |
|
| c45 |
20/300/200/V/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
8057 |
14376 |
24778 |
634 |
628 |
|
| c46 |
20/300/200/F/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
10223 |
11707 |
26118 |
701 |
815 |
|
| c47 |
20/300/200/V/T |
202836 |
202836 |
900 |
12000 |
1800 |
1800 |
12236 |
15756 |
22232 |
688 |
708 |
|
| c48 |
20/300/200/F/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
14142 |
11642 |
24046 |
771 |
788 |
|
| c49 |
30/520/100/V/L |
127 |
127 |
900 |
12000 |
1800 |
1800 |
28 |
69 |
1439 |
222 |
208 |
|
| c50 |
30/520/100/F/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
6591 |
6611 |
15656 |
891 |
489 |
|
| c51 |
30/520/100/V/T |
25 |
25 |
900 |
12000 |
1800 |
1800 |
8 |
19 |
121 |
47 |
43 |
|
| c52 |
30/520/100/F/T |
136296 |
136296 |
900 |
12000 |
1800 |
1800 |
5374 |
3946 |
8074 |
664 |
510 |
|
| c53 |
30/520/400/V/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
7589 |
13609 |
26018 |
793 |
786 |
|
| c54 |
30/520/400/F/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
7354 |
22043 |
34451 |
705 |
631 |
|
| c55 |
30/520/400/V/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
7552 |
32353 |
44761 |
695 |
767 |
|
| c56 |
30/520/400/F/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
8156 |
8180 |
31161 |
671 |
749 |
|
| c57 |
30/700/100/V/L |
24 |
24 |
900 |
12000 |
1800 |
1800 |
17 |
17 |
324 |
40 |
40 |
|
| c58 |
30/700/100/F/L |
15158 |
15158 |
900 |
12000 |
1800 |
1800 |
2581 |
1015 |
6419 |
474 |
480 |
|
| c59 |
30/700/100/V/T |
87 |
87 |
900 |
12000 |
1800 |
1800 |
36 |
38 |
845 |
294 |
224 |
|
| c60 |
30/700/100/F/T |
1551 |
1551 |
900 |
12000 |
1800 |
1800 |
569 |
408 |
8344 |
547 |
426 |
|
| c61 |
30/700/400/V/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
7436 |
12659 |
25127 |
622 |
629 |
|
| c62 |
30/700/400/F/L |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
22397 |
18379 |
29991 |
648 |
640 |
|
| c63 |
30/700/400/V/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
7099 |
19107 |
27031 |
642 |
706 |
|
| c64 |
30/700/400/F/T |
216000 |
216000 |
900 |
12000 |
1800 |
1800 |
12340 |
12340 |
24751 |
661 |
652 |
|
| Average Computation Time |
108330 |
108330 |
900 |
12000 |
1800 |
1800 |
5491 |
7566 |
14503 |
451 |
435 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Gaps of R problem |
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
Upper Bound/
Gurobi/ 60h |
IP search |
Simulated
Annealing |
Branch-and-Price
Guided Search |
Branch-and-Price
Guided Search+ |
Capacity
Scaling and Restricted Branch-and-Bound Matheuristic |
PRL-20-2000 |
Capacity
Scaling and Path Relinking Matheuristic |
Capacity
Scaling and MIP Neighborhood Search |
Capacity
Scaling and MIP Neighborhood Search Tuned |
|
| Gaps |
|
|
0.35% |
|
|
|
|
|
|
|
|
|
|
| Computation Time |
|
|
25929.9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Lower Bound 60h |
|
|
N. Katayama by Gurobi Ver7.51,2018. |
|
|
|
|
|
|
|
| Upper Bound/
Gurobi/ 60h |
|
|
N. Katayama by Gurobi Ver7.51,2018. |
|
|
|
|
|
|
|
| IP search |
|
|
|
M. Hewitt, G.L. Nemhauser, M.W.P. Savelsbergh,
Combining exact and heuristic approaches for the capacitated fixed-charge
network flow problem, INFORMS Journal on Computing, 22, 314–325, 2010. |
| Simulated
Annealing |
|
|
M. Yaghini, M.R.A Kazemzadeh, A simulated
annealing algorithm for unsplittable capacitated network design,
International Journal of Industrial Engineering & Production Research,
23, 91–100, 2012. |
| Branch-and-Price
Guided Search |
|
|
M. Hewitt, G.L. Nemhauser, M.W.P. Savelsbergh,
Branch-and-price guided search for integer programs with an application to
the multicommodity fixed-charge network flow problem, INFORMS Journal on
Computing, 25, 302-316, 2013. |
| Branch-and-Price
Guided Search+ |
|
|
M. Hewitt, G.L. Nemhauser, M.W.P. Savelsbergh,
Branch-and-price guided search for integer programs with an application to
the multicommodity fixed-charge network flow problem, INFORMS Journal on
Computing, 25, 302-316, 2013. |
| Capacity
Scaling and Restricted Branch-and-Bound Matheuristic |
N. Katayama, Unsplittable capacitated network
design problem, Journal of the Faculty of Distribution and Logistics Systems,
Ryutsu Keizei University, 18(1), 1-19, 2013.(in Japanese) |
| Capacity
Scaling and Local Branch Matheuristic |
|
N. Katayama, Unsplittable capacitated network
design problem, Journal of the Faculty of Distribution and Logistics Systems,
Ryutsu Keizei University, 18(1), 1-19, 2013.(in Japanese) |
| Capacity
Scaling and Path Relinking Matheuristic |
|
N. Katayama, Unsplittable capacitated network
design problem, Journal of the Faculty of Distribution and Logistics Systems,
Ryutsu Keizei University, 18(1), 1-19, 2013.(in Japanese) |
| Capacity
Scaling and MIP Neighborhood Search |
|
N. Katayama, Working paper, 2018. |
|
|
|
|
|
|
|
| Capacity
Scaling and MIP Neighborhood Search Tuned |
N. Katayama, Working paper, 2018. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|