Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Theoretical aspects of local search (Monographs in Theoretical Computer Science)
Michiels W., Aarts E., Korst J., Springer-Verlag New York, Inc., Secaucus, NJ, 2007. 238 pp. Type: Book (9783540358534)
Date Reviewed: Jun 1 2007

In the last half-century, local search methodologies have become very popular for finding, with a “reasonable” computational cost, approximate but often very good solutions to hard optimization problems that cannot be solved exactly, due to the size of the search space. Most of them arise from the progressive improvement of the best-known solution of the problem at hand, obtained through iterative neighborhood-based changes performed on one solution (or several), that can initially be chosen at random. Some of these local search methods are heuristics specialized for one particular problem, such as traveling salesman or job-shop scheduling; others, called metaheuristics, seek to solve, ideally, any combinatorial optimization problem. The most famous of these are simulated annealing, tabu search, genetic algorithms, ant colony, and particle swarm algorithms.

There exist a huge number of papers on local search methods, most of which are of an empirical nature. Theoretical works exist, however, and this book is among them. The book focuses on three main topics: performance guarantees, investigations of time complexity, and asymptotic convergence studies in the case where a probabilistic iteration mechanism is applied.

The book contains eight chapters. In the introductory chapter 1, the authors position local search within the field of combinatorial optimization, and present basic definitions and terminology. Chapter 2 describes basic neighborhood functions for a number of classical combinatorial optimization problems: the traveling salesman problem, machine scheduling, the Steiner tree problem in graphs, graph coloring, and uniform graph partitioning. In the last subsection, the authors discuss an interesting link between local search in combinatorial optimization and the search for stable configurations in Hopfield neural networks. Chapter 3 illustrates the use of indirect solution representations for various machine scheduling problems; two problems are stressed: the sum of weighted completion time on unrelated machines, and symmetric earliness and tardiness on a single machine. Chapter 4 discusses properties of neighborhood graphs, as well as dominance relations between different neighborhood functions for the traveling salesman and job-shop scheduling problems. More specifically, the authors prove properties of the diameter and the connectivity of neighborhood graphs, and relate the neighborhood graphs of different neighborhood functions.

In chapter 5, the authors give several examples of performance guarantees for local minima of given neighborhood functions, and show, for some specific examples, that local optimality implies global optimality. In particular, they discuss exact neighborhood functions, performance ratios of neighborhood functions, nonapproximability results, and the way to obtain polynomial-time algorithms from neighborhood functions. Chapter 6 addresses the computational complexity of finding a local optimum for a given combinatorial optimization problem and a given neighborhood function. A general theory has been developed on the time complexity of local search. This theory is the local search counterpart of the famous theory of nondeterministic polynomial time (NP) completeness. It can be used to prove the intractability of finding a local optimum for some local search problems. The chapter discusses the complexity class polynomial-time local search (PLS), and gives examples of PLS-complete problems and related PLS reductions. In chapter 7, the authors discuss metaheuristics that potentially give higher-quality solutions, either by allowing nonimproving moves, or through the use of multiple runs. The authors focus on some of these techniques, namely, simulated annealing, tabu search, random restart, greedy randomized adaptive search procedure (GRASP), iterated local search, and genetic local search. Finally, chapter 8 discusses the asymptotic convergence of simulated annealing using the theory of Markov chains. The authors describe the mathematical modeling of the method, and discuss the convergence of simulated annealing in both the framework of the theory of homogeneous Markov chains and the theory of inhomogeneous Markov chains. The chapter also includes a short description of a nonconvergence result for tabu search. The book ends with three appendices devoted to graph theory, complexity theory, and approximation algorithms, and a list of local search problems that have been proven to be PLS complete.

Overall, this book brings to its readers many fresh ideas in the field of local search. The book deserves attention; it shows that theoretical works are present in a field overwhelmed by experimental studies. The book is very well written, and authored by well-known researchers involved in the field. I feel that readers will be particularly interested in chapter 6, since the theory of PLS-completeness is not common in the literature. At the opposite end, chapter 8, devoted to the convergence of simulated annealing, is less original, since it relates works that are now a little dated, and that did not lead to better implementations of the method. The global coherence of the book might have been improved if the authors had added a conclusion, to recapitulate the main relevant contributions included in the book. However, the book will be very useful for researchers, students, and engineers involved in optimization.

Reviewer:  Patrick Siarry Review #: CR134345 (0805-0436)
Bookmark and Share
  Editor Recommended
 
 
Optimization (G.1.6 )
 
 
General (G.2.0 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Problem Solving, Control Methods, And Search (I.2.8 )
 
Would you recommend this review?
yes
no
Other reviews under "Optimization": Date
A general-purpose global optimizer: implementation and applications
Pronzato L., Walter E., Venot A., Lebruchec J. Mathematics and Computers in Simulation XXVI(5): 412-422, 1984. Type: Article
Jul 1 1985
Minkowski matrices.
Cryer C. ACM Transactions on Mathematical Software 9(2): 199-214, 1983. Type: Article
Feb 1 1985
Numerical optimization techniques
Evtushenko Y., Springer-Verlag New York, Inc., New York, NY, 1985. Type: Book (9789780387909493)
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy