Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(13)
Configuration Space
Global Change
Graph Partitioning
Low Temperature
Power Optimization
Public Libraries
Random Graph
Simulated Annealing
Traveling Salesman
Traveling Salesman Problem
lin kernighan
Local Search
Markov Chain
Subscribe
Academic
Publications
Combining simulated annealing with local search heuristics
Combining simulated annealing with local search heuristics,10.1007/BF02601639,Annals of Operations Research,Olivier C. Martin,Steve W. Otto
Edit
Combining simulated annealing with local search heuristics
(
Citations: 91
)
BibTex

RIS

RefWorks
Download
Olivier C. Martin
,
Steve W. Otto
We introduce a metaheuristic to combine
simulated annealing
with
local search
methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either
simulated annealing
or local search. The main idea is to embed deterministic
local search
techniques into
simulated annealing
so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this metaheuristic for the
traveling salesman
and
graph partitioning
problems. Tests on instances from
public libraries
and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon
local search
methods very significantly. For the
traveling salesman problem
with randomly distributed cities, in a square, the procedure improves on 3opt by 1.6%, and on LinKernighan
local search
by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over KernighanLin
local search
is 8.9%. For both CO problems, we obtain new best heuristics.
Journal:
Annals of Operations Research  Annals OR
, vol. 63, no. 1, pp. 5775, 1996
DOI:
10.1007/BF02601639
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
Citation Context
(50)
...These include methods such as variable neighborhood descent [5, 36, 47, 64, 65, 67], variable neighborhood search [9, 11, 17, 23, 36, 51], shortterm memory tabu search [1, 15, 16, 29, 30, 40, 42, 43, 49, 55, 68, 69], simulated annealing [14, 39, 44], iterated local search [6, 7, 8, 38,
45
, 46, 66], and verylarge scale neighborhood search [2, 3, 28], that explore beyond the current solution’s...
MAURICIO G. C. RESENDE
,
et al.
GRASP: GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
...The main theme of ITS is the concept of intensification and reconstruction (I and R). The early origin of this concept goes two decades back and since then, various modifications of the basic idea have been proposed, among them are: iterated LinKernighan algorithm [36], combined with the local search [37], TS based on "ruin and recreate" principle [
38
], and combined with an iterated local search [39, 40]...
Surya Prakash Singh
.
Solving Facility Layout Problem: Threelevel Tabu Search Metaheuristic...
...For examples of successful applications of ILS we refer the interested reader to [
67
, 60, 65, 22]...
Christian Blum
,
et al.
Hybrid Metaheuristics: An Introduction
...This can be found e.g., in the work of
Martin and Otto (1996)
on the TSP, which incorporates local moves known as 4opt moves within a simulated annealing framework...
Colin G. Johnson
.
A design framework for metaheuristics
...The ILS (Iterated Local Search) metaheuristic [
21
, 22] starts from a locally optimal feasible solution...
Celso C. Ribeiro
,
et al.
Heuristics for the mirrored traveling tournament problem
References
(26)
Partitioning of unstructured meshes for load balancing
(
Citations: 28
)
Olivier C. Martin
,
Steve W. Otto
Journal:
Concurrency and Computation: Practice and Experience  CONCURRENCY
, vol. 7, no. 4, pp. 303314, 1995
Optimization by Simmulated Annealing
(
Citations: 3074
)
Scott Kirkpatrick
,
D. Gelatt Jr.
,
Mario P. Vecchi
Journal:
Science
, vol. 220, no. 4598, pp. 671680, 1983
LargeStep Markov Chains for the Traveling Salesman Problem
(
Citations: 168
)
Olivier Martin
,
Steve W. Otto
,
Edward W. Felten
Published in 1991.
Integrated PVM Framework Supports Heterogeneous Network Computing
(
Citations: 101
)
Jack J. Dongarra
,
G. a. Geist
,
V. s. Sunderam
Published in 1993.
Largestep markov chains for the TSP incorporating local search heuristics
(
Citations: 99
)
O. Martin
,
S. Otto
,
E. Felten
Journal:
Operations Research Letters  ORL
, vol. 11, no. 4, pp. 219224, 1992
Sort by:
Citations
(91)
Parallelized genetic ant colony systems for solving the traveling salesman problem
ShyiMing Chen
,
ChihYao Chien
Journal:
Expert Systems With Applications  ESWA
, vol. 38, no. 4, pp. 38733883, 2011
An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion
(
Citations: 13
)
Xingye Dong
,
Houkuan Huang
,
Ping Chen
Journal:
Computers & Operations Research  CoR
, vol. 36, no. 5, pp. 16641669, 2009
GRASP: GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
MAURICIO G. C. RESENDE
,
RICARDO M. A. SILVA
Published in 2009.
Solving Facility Layout Problem: Threelevel Tabu Search Metaheuristic Approach
Surya Prakash Singh
Published in 2009.
Hybrid Metaheuristics: An Introduction
(
Citations: 9
)
Christian Blum
,
Andrea Roli
Conference:
Hybrid Metaheuristics  HM
, 2008