Information Technology Reference
In-Depth Information
Even if the warm starting procedure allows the IPWS model to find an initial
solution to all the instances, in only 69 of the 80 instance the solution is further
improved, and only 9 are solved to optimality. Figure 4 compares the performance
of the LNS and the IPWS in those 69 instances (after an initial solution has been
found). The graph shows how the average objective value decreases in time.
Figure 4 (a) shows how the LNS outperforms the IPWS within the 600 seconds
time-limit. It is worth noticing that most of the optimization is done within 100
seconds. This suggests that the neighborhood used converges fast towards a local
minima from which it cannot escape. This result is confirmed in Figure 4 (b)
where it is possible to see that the LNS is outperformed by the IPWS after ca.
1600 seconds.
180000
240000
LNS
IP
LNS
IP
220000
160000
200000
140000
180000
120000
160000
100000
140000
80000
120000
60000
100000
40000
80000
20000
60000
0
40000
0
100
200
300
400
500
600
0
500 1000 1500 2000 2500 3000 3500 4000
Runtime (sec.)
Runtime (sec.)
(a)
(b)
Fig. 4.
Convergency of the algorithms in (a) 600 sec. (b) 3600 sec. Data is collected
only for the instances where the IPWS improves the initial solution.
Figure 5 shows how the warm-starting procedure leads to better solutions. We
compare the LNS that uses the warm-starting procedure, with a version of the
LNS where the initial solution is given by solving[M U0 the IP model without
the objective function.
92000
LNS without warm-start
LNS
90000
88000
86000
84000
82000
80000
78000
76000
74000
72000
70000
0
100
200
300
400
500
600
Runtime (sec.)
Fig. 5.
Impact of the warm-start procedure. Comparing the LNS with a modified
version that does not use the warm-start procedure.
