Some convergence results on probabilistic Tabu Search

U. Faigle, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

53 Citations (Scopus)
85 Downloads (Pure)


During recent years, much work has gone into the exploration of general fundamental principles underlying local search strategies for combinatorial optimization. Many of these strategies can be subsumed under the general framework of Tabu Search, which introduces mechanisms of guidance and control based on flexible memory processes, broadening the range of strategic possibilities beyond those incorporated in memoryless search heuristics such as Simulated Annealing. We consider some examples of such memory based strategies for modifying both the generation and acceptance probabilities and investigate their impact on convergence results. It turns out that several Tabu Search ideas can be subjected to mathematical analyses similar to those applied to Simulated Annealing, making it possible to establish corresponding convergence properties based on a broader foundation.
Original languageUndefined
Pages (from-to)32-37
Number of pages6
JournalORSA journal on computing
Issue number1
Publication statusPublished - 1992


  • METIS-140517
  • IR-98450

Cite this