Using Markov chains to analyze the effectiveness of local search algorithms

DOI10.1016/J.DISOPT.2010.07.002zbMATH Open1241.90089OpenAlexW2089414113MaRDI QIDQ429676FDOQ429676

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

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

zbMATH Keywords

aggregationheuristicslocal searchdiscrete optimizationstate reductionlumpingtravelling salesman problemMarkov chain analysisLin-Kernighan-Helsgaun algorithm

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• TSPLIB—A Traveling Salesman Problem Library
• Title not available (Why is that?)
• Optimization by simulated annealing
• Title not available (Why is that?)
• A method for solving traveling-salesman problems
• Title not available (Why is that?)
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• 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
• Simulating Stable Stochastic Systems: III. Regenerative Processes and Discrete-Event Simulations
• Finite-time performance analysis of static simulated annealing algorithms

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A framework for analyzing sub-optimal performance of local search algorithms
• Markov chain modelling of the solution surface in local search
• Visiting near-optimal solutions using local search algorithms

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)