| Hop-Constrained network design |
Results for C
Instances |
2017/10/30 |
|
|
|
|
|
|
|
|
|
|
|
|
| Problem |
Problem |
Lower Bound/
Gurobi/ 30h |
Upper Bound/
Gurobi/ 30h |
Capacity
Scaling and Restricted Branch-and-Bound Matheuristic |
Capacity
Scaling and Local Branch Matheuristic |
Capacity
Scaling and MIP Neighborhood Search |
Capacity
Scaling and MIP Neighborhood Search Tuned |
|
|
|
|
|
|
|
|
|
| Year |
|
2017 |
2017 |
2017 |
2017 |
2017 |
2017 |
|
|
|
|
|
|
|
|
|
| c100_400_10_V_L_10.dow |
|
29016.0 |
29016.0 |
29242 |
29016 |
29016 |
29016 |
|
|
|
|
|
|
|
|
|
| c100_400_30_F_L_10.dow |
|
56260.0 |
56260.0 |
59262 |
56260 |
56405 |
56260 |
|
|
|
|
|
|
|
|
|
| c33 |
20/230/040/V/L |
424075.0 |
424075.0 |
424075 |
424075 |
424075 |
424075 |
|
|
|
|
|
|
|
|
|
| c35 |
20/230/040/V/T |
374013.0 |
374013.0 |
375326 |
374013 |
374013 |
374013 |
|
|
|
|
|
|
|
|
|
| c36 |
20/230/040/F/T |
644361.0 |
644361.0 |
646958 |
644361 |
644361 |
644361 |
|
|
|
|
|
|
|
|
|
| c37 |
20/230/200/V/L |
104072.0 |
104072.0 |
104776.5 |
104072 |
104072 |
104072 |
|
|
|
|
|
|
|
|
|
| c38 |
20/230/200/F/L |
160969.0 |
160969.0 |
163240 |
160969 |
160969 |
160969 |
|
|
|
|
|
|
|
|
|
| c39 |
20/230/200/V/T |
105729.0 |
105729.0 |
106179 |
105729 |
105729 |
105729 |
|
|
|
|
|
|
|
|
|
| c40 |
20/230/200/F/T |
144587.0 |
144587.0 |
144635 |
144587 |
144587 |
144587 |
|
|
|
|
|
|
|
|
|
| c41 |
20/300/040/V/L |
429700.0 |
429700.0 |
429700 |
429700 |
429700 |
429700 |
|
|
|
|
|
|
|
|
|
| c42 |
20/300/040/F/L |
588325.0 |
588325.0 |
590157 |
588325 |
588325 |
588325 |
|
|
|
|
|
|
|
|
|
| c43 |
20/300/040/V/T |
464550.0 |
464550.0 |
464569 |
464550 |
464550 |
464550 |
|
|
|
|
|
|
|
|
|
| c44 |
20/300/040/F/T |
604237.0 |
604237.0 |
604997 |
604237 |
604237 |
604237 |
|
|
|
|
|
|
|
|
|
| c45 |
20/300/200/V/L |
78649.0 |
78649.0 |
78739 |
78649 |
78705 |
78649 |
|
|
|
|
|
|
|
|
|
| c46 |
20/300/200/F/L |
122151.0 |
122151.0 |
122597 |
122151 |
122151 |
122151 |
|
|
|
|
|
|
|
|
|
| c47 |
20/300/200/V/T |
78242.0 |
78242.0 |
78250 |
78242 |
78242 |
78242 |
|
|
|
|
|
|
|
|
|
| c48 |
20/300/200/F/T |
111729.7 |
111729.7 |
111736.8 |
111729.7 |
112030 |
111729.67 |
|
|
|
|
|
|
|
|
|
| c49 |
30/520/100/V/L |
54586.0 |
54586.0 |
54650 |
54586 |
54586 |
54586 |
|
|
|
|
|
|
|
|
|
| c50 |
30/520/100/F/L |
99745.0 |
99745.0 |
101311 |
99745 |
99745 |
99745 |
|
|
|
|
|
|
|
|
|
| c51 |
30/520/100/V/T |
52439.0 |
52439.0 |
52691 |
52439 |
52439 |
52439 |
|
|
|
|
|
|
|
|
|
| c52 |
30/520/100/F/T |
97784.9 |
98087.0 |
98853 |
98087 |
98238 |
98087 |
|
|
|
|
|
|
|
|
|
| c53 |
30/520/400/V/L |
115313.1 |
115313.1 |
115350.5 |
115313.1 |
115427.67 |
115313.14 |
|
|
|
|
|
|
|
|
|
| c54 |
30/520/400/F/L |
155328.3 |
156028.2 |
156544 |
156266.3 |
156260.2 |
156199.14 |
|
|
|
|
|
|
|
|
|
| c55 |
30/520/400/V/T |
116650.3 |
116650.3 |
116722.2 |
116650.3 |
116685.74 |
116685.74 |
|
|
|
|
|
|
|
|
|
| c56 |
30/520/400/F/T |
155299.8 |
156311.2 |
156883.3 |
156311.2 |
156373 |
156368.93 |
|
|
|
|
|
|
|
|
|
| c57 |
30/700/100/V/L |
48693.0 |
48693.0 |
48770 |
48693 |
48693 |
48693 |
|
|
|
|
|
|
|
|
|
| c58 |
30/700/100/F/L |
61144.0 |
61144.0 |
61226 |
61144 |
61144 |
61144 |
|
|
|
|
|
|
|
|
|
| c59 |
30/700/100/V/T |
46341.0 |
46341.0 |
46454 |
46341 |
46341 |
46341 |
|
|
|
|
|
|
|
|
|
| c60 |
30/700/100/F/T |
55960.0 |
55960.0 |
56595 |
55965 |
56213 |
55960 |
|
|
|
|
|
|
|
|
|
| c61 |
30/700/400/V/L |
100875.0 |
100875.0 |
101321 |
100875 |
100875.6 |
100875 |
|
|
|
|
|
|
|
|
|
| c62 |
30/700/400/F/L |
139637.4 |
142881.2 |
143112 |
142905 |
143037.83 |
142892.5 |
|
|
|
|
|
|
|
|
|
| c63 |
30/700/400/V/T |
96500.5 |
96500.5 |
96584 |
96500.5 |
96500.5 |
96500.5 |
|
|
|
|
|
|
|
|
|
| c64 |
30/700/400/F/T |
132960.5 |
134238.7 |
134661.8 |
134255.2 |
134538.25 |
134462.25 |
|
|
|
|
|
|
|
|
|
| Average
Gap |
|
- |
0.14% |
0.65% |
0.15% |
0.20% |
0.15% |
|
|
|
|
|
|
|
|
|
| Average
Computation Time |
|
- |
26937.5
|
120.4
|
2055.3
|
204.5
|
182.4
|
|
|
|
|
|
|
|
|
|
| Hop Constraint
Parameter of Commodities: (the length of a shortest path between origin nodes
and destination nodes) + 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Lower Bound/ Gurobi/ 30h |
|
|
N. Katayama by Gurobi Ver7.51,2017. |
|
|
|
|
|
|
|
|
|
|
|
| Upper Bound/ Gurobi/ 30h |
|
|
N. Katayama by Gurobi Ver7.51,2017. |
|
|
|
|
|
|
|
|
|
|
|
| Capacity Scaling
and Restricted Branch-and-Bound Matheuristic |
N. Katayama, A combined capacity scaling and
local branching matheuristic for the hop-constrained multicommodity network
design problem, Far East Journal
of Applied Mathematics, .94(3), 185-215, 2016. |
| Capacity Scaling
and Local Branch Matheuristic |
|
N. Katayama, A combined capacity scaling and
local branching matheuristic for the hop-constrained multicommodity network
design problem, Far East Journal
of Applied Mathematics, .94(3), 185-215, 2016. |
| Capacity Scaling
and MIP Neighborhood Search |
|
N. Katayama, Working paper, 2017. |
|
|
|
|
|
|
|
|
|
|
|
|
| min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Greedy 0.100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Greedy 0.700 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Greedy BINARY 0.100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Greedy BINARY 0.700 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Greedy 最小 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 差 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Capacity Scaling
and MIP Neighborhood Search Tuned |
N. Katayama, Working paper, 2017. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|