Paper Info
Title
A local search template
Abstract
Many problems in combinatorial optimization are NP-hard which implies that it is generally believed that no algorithms exist that solve each instance of such a problem to optimality using a running time that can be bounded by a polynomial in the instance size. As a consequence, much effort has been devoted to the design and analysis of algorithms that can find high quality approximative solutions in reasonable, i.e. polynomial, running times. Many of these algorithms apply some kind of neighborhood search and over the years a great variety of such local search algorithms have been proposed, applying different kinds of search strategies often inspired by optimization processes observed in nature. The purpose of this paper is to capture within a single template the common features of the best-known local search algorithms. The template is also used for the purpose of indicating directions for novel algorithmic ideas in the area of local search. A template is presented that captures a vast majority of the local search algorithms proposed in the literature, including iterative improvement, simulated annealing, threshold accepting, tabu search and genetic algorithms. The template leads to a classification of existing local search algorithms and offers the possibility to fit in new types of local search approaches.
Year
DOI
Venue
1992
10.1016/S0305-0548(97)00093-2
Computers and Operations Research
Keywords
DocType
Volume
tabu search,threshold accepting,genetic algorithms,simulated annealing,local search template,iterative improvement,local search,search algorithm,genetic algorithm
Conference
25
Issue
ISSN
Citations 
11
0305-0548
22
PageRank 
References 
Authors
2.35
8
3
Name
Order
Citations
PageRank
R. J. M. Vaessens1445.20
Emile H. L. Aarts21641307.48
J. K. Lenstra31689329.39