Information Technology Reference
In-Depth Information
6.2 Computational Study: E
ciency
Each instance was solved using the dual ascent approach ((
DA
)with(
CG
)) as
describedinSection5.ResultsarereportedinTable2.Thenumberofiterations
refers to the number of times the restricted master problem (
RM
)wassolved
(Step 1 in (
DA
)) until the solution converges. We also report the solution time for
solving the first (
RM
) (with no constraints (23)), the total time spent in solving
(
RM
) for all the iterations, and the total computational time until convergence.
Tabl e 2.
Numbers of iterations and solution times for the computational instances
Number of Solution time for Solution time for
Total
Instance
|
I
||
J
|
D
iterations 1st (
RM
) (sec) all (
RM
) (sec) time (sec)
1a
30 50 3
4
0.44
0.48
4
1b
30 50 6
7
0.44
0.69
6
1c
30 50 9
9
0.42
0.59
9
2a
30 100 3
6
6.53
9.54
32
2b
30 100 6
4
6.53
250.67
266
2c
30 100 9
5
6.55
6.91
25
3a
40 80 3
3
269.59
269.65
279
3b
40 80 6
8
269.72
274.41
308
3c
40 80 9
8
269.58
272.18
305
4a
40 100 3
3
2114.75
2114.77
2139
4b
40 100 6
4
2164.36
2169.6
2203
4c
40 100 9
7
2145.64
2185.57
2243
5a
50 100 3
3
18.58
18.60
69
5b
50 100 6
5
18.48
22.65
133
5c
50 100 9
7
18.55
24.71
167
6a
50 150 3
3
521.77
521.83
889
6b
50 150 6
3
507.01
507.06
896
6c
50 150 9
6
506.19
533.02
1443
7a
60 100 3
5
299.47
300.05
492
7b
60 100 6
5
299.63
304.98
466
7c
60 100 9
5
311.05
315.80
457
The results indicate that the proposed algorithm ((
DA
) together with (
CG
))
converges very quickly — with fewer than 10 iterations in all instances — due
to the strength of the cuts generated in (
CG
). Interestingly, the computational
time does not increase monotonically as
D
increases. In several cases when the
damage is low or severe, perhaps the low-cost options are
easier
to identify, the
solution converges quickly. When the damage is moderately high, many different
subsets of centres may have comparable costs, and the algorithm takes a longer
time to determine the optimal solution.
We also note that a major proportion of computational effort is spent on
solving the (
RM
)s, in particular the first (
RM
). Since the first restricted master
problem does not contain constraints (23), it is equivalent to determining centre
locations and inventory pre-positioning without consideration of
Recovery Cost
.
