Supporting material for the article:

Estimation-based Local Search
for Stochastic Combinatorial Optimization

January 2007

1. Abstract:

In recent years, growing attention has been devoted to the development of metaheuristics and local search for tackling stochastic combinatorial optimization problems. This paper focuses on local search, which is particularly useful for improving the quality of the solutions found by metaheuristics. The effectiveness of a local search is greatly determined by the evaluation procedure that is used to select the best of several solutions in the presence of uncertainty. In this paper, we propose an effective evaluation procedure in which the solutions are evaluated by empirical estimation techniques. We illustrate our approach and assess its performance with the Probabilistic Travelling Salesman Problem. Experimental results on a large set of instances show that our approach can lead to a very fast and highly effective local search.

2. Algorithms:

• 2-p-opt and 1-shift: The state-of-the-art iterative improvement algorithms for PTSP
• 2.5-opt-ACs: 2.5-opt neighborhood exploration and neighborhood reduction techniques(fixed-radius search, candidate lists and don’t look bits) in the analytical computation framework.
• 2.5-opt-EEs: 2.5-opt neighborhood exploration and neighborhood reduction techniques(fixed-radius search, candidate lists and don’t look bits) in the empirical estimation framework.
  • 2.5-opt-EEs-10: 2.5-opt-EEs with 10 realizations
  • 2.5-opt-EEs-100: 2.5-opt-EEs with 100 realizations
  • 2.5-opt-EEs-1000: 2.5-opt-EEs with 1000 realizations
  • 2.5-opt-EEs-100-ri: 2.5-opt-EEs in which a set of realizations is sampled anew each time an improved solution is found
  • 2.5-opt-EEs-100-rc: 2.5-opt-EEs in which a set of realizations is sampled anew for each comparision
• ILS-2.5-opt-ACs: Iterated local search with 2.5-opt-ACs
• ILS-2.5-opt-EEs: Iterated local search with 2.5-opt-EEs
  • ILS-2.5-opt-EEs-100: ILS-2.5-opt-EEs with 100 realizations
  • ILS-2.5-opt-EEs-1000: ILS-2.5-opt-EEs with 1000 realizations

3. PTSP Instances :

The problems considered are homogeneous PTSP instances obtained from TSP instances generated by the DIMACS generator. We carried out experiments with two classes of instances. In the first, nodes are uniformly distributed, in the second they are clustered. For each of the two experiments, we consider 100 TSP instances of size 100, 200, 300, and 1000 nodes. From each TSP instance we obtain 9 PTSP instances by letting the probability range in [0.1, 0.9] with a step size of 0.1:

5. Experiments on neighborhood-reduction techniques

Experimental results on clustered homogeneous PTSP instances of size 100. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on clustered homogeneous PTSP instances of size 200. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on clustered homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 100. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 200. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2-p-opt and 1-shift normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

6. Experiments to assess the estimation approach

Experimental results on clustered homogeneous PTSP instances of size 100. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on clustered homogeneous PTSP instances of size 300. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

Experimental results on clustered homogeneous PTSP instances of size 200. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on clustered homogeneous PTSP instances of size 200. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

Experimental results on clustered homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on clustered homogeneous PTSP instances of size 300. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

Experimental results on uniform homogeneous PTSP instances of size 100. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 300. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

Experimental results on uniform homogeneous PTSP instances of size 200. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 200. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

Experimental results on uniform homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100 normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 300. For the normalized values shown in the previous plot, the difference between 2.5-opt-EEs-100 and 2.5-opt-ACs over time is computed and the 5%, 25%, 50%, 75%, and 95% quantiles of the distribution of the differences are plotted. For a curve, a value greater than zero indicates that 2.5-opt-EEs-100 is better than 2.5-opt-ACs and vice versa.

6. Experiments on large instances

Experimental results on clustered homogeneous PTSP instances of size 1000. The plots represent the cost of the solutions obtained by 2.5-opt-EEs-10, 2.5-opt-EEs-100, 2.5-opt-EEs-1000, 1-shift, and 2-p-opt normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum. Note that the algorithms based on the analytical computation techniques do not produce meaningful results for p>0.5 due to the numerical problem. The algorithms based on the empirical estimation do not suffer from this problem.

Experimental results on uniform homogeneous PTSP instances of size 1000. The plots represent the cost of the solutions obtained by 2.5-opt-EEs-10, 2.5-opt-EEs-100, 2.5-opt-EEs-1000, 1-shift, and 2-p-opt normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum. Note that the algorithms based on the analytical computation techniques do not produce meaningful results for p>0.5 due to the numerical problem. The algorithms based on the empirical estimation do not suffer from this problem.

6. Experiments on sampling strategies

Experimental results on clustered homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100, 2.5-opt-EEs-100-ri, and 2.5-opt-EEs-100-rc normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

Experimental results on uniform homogeneous PTSP instances of size 300. The plots represent the average cost of the solutions obtained by 2.5-opt-EEs-100, 2.5-opt-EEs-100-ri, and 2.5-opt-EEs-100-rc normalized by the one obtained by 2.5-opt-ACs. Each algorithm is stopped when it reaches a local optimum.

7. Experiments on iterated local search

Experimental results on clustered homogeneous PTSP instances of size 1000. The plots represent the cost of the solutions obtained by ILS-2.5-opt-EEs-100 and ILS-2.5-opt-EEs-1000 normalized by the one obtained by ILS-2.5-opt-ACs. Note that the algorithms based on the analytical computation techniques do not produce meaningful results for p>0.5 due to the numerical problem. The algorithms based on the empirical estimation do not suffer from this problem.

Experimental results on uniform homogeneous PTSP instances of size 1000. The plots represent the cost of the solutions obtained by ILS-2.5-opt-EEs-100 and ILS-2.5-opt-EEs-1000 normalized by the one obtained by ILS-2.5-opt-ACs. Note that the algorithms based on the analytical computation techniques do not produce meaningful results for p>0.5 due to the numerical problem. The algorithms based on the empirical estimation do not suffer from this problem.

7. Numerical values and statistical results:

We also provide the absolute values for all the results in the form of tables. In these tables, we present the final solution quality and the corresponding computational time for each probabiltiy range. Moreover, in order to test that the observed difference between the cost of the solutions reached by the considered algorithms are significant in a statistical sense, we use a non-parametric test known as Wilcoxon test. We present the p-values obtained from the Wilcoxon test. Please note that all statistics shown in the table are given for 100 instances at each probability level. The results are composed in a single pdf file:

Format
PDF	(click the above icon to see/download the results)