Using Markov chains to analyze the effectiveness of local search algorithms

This paper analyzes the performance of local search algorithms (guided by the best-to-date solution at each iteration) in visiting suboptimal solutions for hard discrete optimization problems. The β-acceptable solution concept is used to capture how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future in visiting suboptimal solutions. By this concept, an algorithm run is deemed a success if it reaches the level β, where β denotes an objective function value close to but still worse than the globally optimal value. A Markov chain state space reduction technique, state pooling, is introduced and used to obtain an estimator for the expected number of iterations to visit a β-acceptable solution. Convergence results for this estimator are provided. Computational experiments with the LinKernighanHelsgaun algorithm applied to medium and large travelling salesman problem instances taken from TSPLIB (all with known optimal solutions) are reported to illustrate the application of this estimator.