Using Markov chains to analyze the effectiveness of local search algorithms

DOI10.1016/J.DISOPT.2010.07.002MaRDI QIDQ429676zbMATH OpenOpenAlexFDO

Authors Alexander G. Nikolaev, Sheldon H. Jacobson

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

aggregationdiscrete optimizationheuristicsLin-Kernighan-Helsgaun algorithmlocal searchlumpingMarkov chain analysisstate reductiontravelling salesman problem

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• A framework for analyzing sub-optimal performance of local search algorithms
• Visiting near-optimal solutions using local search algorithms
• Markov chain modelling of the solution surface in local search
• scientific article; zbMATH DE number 23663
• scientific article; zbMATH DE number 1054958

Cites work

• A finite characterization of weak lumpable Markov processes. I: The discrete time case
• A method for solving traveling-salesman problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Finite-time performance analysis of static simulated annealing algorithms
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• Optimization by simulated annealing
• Simulating Stable Stochastic Systems: III. Regenerative Processes and Discrete-Event Simulations
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(5)

• Visiting near-optimal solutions using local search algorithms
• scientific article; zbMATH DE number 1054958 (Why is no real title available?)
• Markov chain modelling of the solution surface in local search
• A framework for analyzing sub-optimal performance of local search algorithms
• scientific article; zbMATH DE number 2226659 (Why is no real title available?)

Describes a project that uses

Uses Software

• TSPLIB
• LKH
• Tabu search

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429676)