  Local search metaheuristics like tabu search or simulated annealing are
popular heuristic optimization algorithms for finding near-optimal solutions
for combinatorial optimization problems. However, it is still challenging for
researchers and practitioners to analyze their behaviour and systematically
choose one over a vast set of possible metaheuristics for the particular
problem at hand. In this paper, we introduce a theoretical framework based on
Markov Decision Processes (MDP) for analyzing local search metaheuristics. This
framework not only helps in providing convergence results for individual
algorithms, but also provides an explicit characterization of the
exploration-exploitation tradeoff and a theory-grounded guidance for
practitioners for choosing an appropriate metaheuristic for the problem at
hand. We present this framework in detail and show how to apply it in the case
of hill climbing and the simulated annealing algorithm.
