Using Markov chains to analyze the effectiveness of local search algorithms

DOI10.1016/J.DISOPT.2010.07.002zbMath1241.90089OpenAlexW2089414113MaRDI QIDQ429676

Alexander G. Nikolaev, Jacobson, Sheldon H.

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.07.002

zbMATH Keywords

aggregationheuristicslocal searchtravelling salesman problemdiscrete optimizationstate reductionlumpingMarkov chain analysisLin-Kernighan-Helsgaun algorithm

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (1)

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

Uses Software

• TSPLIB
• LKH
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• A finite characterization of weak lumpable Markov processes. I: The discrete time case
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• TSPLIB—A Traveling Salesman Problem Library
• Simulating Stable Stochastic Systems: III. Regenerative Processes and Discrete-Event Simulations
• A Method for Solving Traveling-Salesman Problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Finite-time performance analysis of static simulated annealing algorithms

This page was built for publication: Using Markov chains to analyze the effectiveness of local search algorithms