A framework for analyzing sub-optimal performance of local search algorithms

Alexander G. Nikolaev, Sheldon H. Jacobson, Shane N. Hall, Darrall Henderson

Research output: Contribution to journalArticlepeer-review


This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan- Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.

Original languageEnglish (US)
Pages (from-to)407-433
Number of pages27
JournalComputational Optimization and Applications
Issue number3
StatePublished - Jul 2011


  • Convergence
  • Discrete optimization
  • Finite-time performance
  • Heuristics
  • Lin-Kernighan-Helsgaun algorithm
  • Local search
  • Simulated annealing
  • Tabu search
  • Traveling salesman problem

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'A framework for analyzing sub-optimal performance of local search algorithms'. Together they form a unique fingerprint.

Cite this