Using Markov chains to analyze the effectiveness of local search algorithms

Alexander G. Nikolaev, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)160-173
Number of pages14
JournalDiscrete Optimization
Issue number2
StatePublished - May 2011


  • Aggregation
  • Discrete optimization
  • Heuristics
  • LinKernighanHelsgaun algorithm
  • Local search
  • Lumping
  • Markov chain analysis
  • State reduction
  • Travelling salesman problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Using Markov chains to analyze the effectiveness of local search algorithms'. Together they form a unique fingerprint.

Cite this