This book clearly defines and describes the multitude of stochastic local search (SLS) methods, and their similarities and differences, and analyzes the techniques so that researchers, students, and engineers can better tailor these methods to practical applications, while solving various hard combinatorial problems.
The SLS methods outlined in the book (defined in chapter 2) are divided into three categories: simple local searches, hybrid local searches, and population-based methods. Specifically, these methods include the following algorithms: iterative improvement (II), randomized iterative improvement (RII), variable neighborhood descent (VND), variable depth search (VDS), simulated annealing (SA), tabu search (TS), dynamic local search (DLS), iterated local search (ILS), greedy randomized adaptive search procedure (GRASP), adaptive iterated construction search (AICS), ant colony optimization (ACO), and memetic algorithms (MA). The variety of methods is quite expansive; perhaps an extra category should have been included to further divide the simple methods into local and global searches, thus differentiating the iterated improvement methods (typically local) from those like the simulated annealing approach (generally global).
The authors illustrate the methods by choosing popular problems familiar to any reader, whether she or he is an educator or computer engineer. For example, the traveling salesperson problem (TSP) is used to elucidate the II, ACO, AICS, RII, DLS, and ILS methods. Similarly, the propositional satisfiability problem (SAT), which is the first known nonpolynomial time (NP) complete problem, is used to elucidate the II, RII, DLS, MA, GRASP, and TS algorithms.
Pseudocode algorithms, figures, and proofs accompany each of the SLS methods. This enhances the reader’s understanding of the procedure, and enables the reader to compare the iterative steps and performances along the way. For each search method, an algorithmic analysis is presented. Afterward, the authors introduce other interesting relationships and concepts. For example, they create an alternative approach to expound on constructive searches by adding “backtracking or recursive mechanisms.” This yields a complete systematic search that clearly impacts the optimization of the problem, requiring exponential time. The authors use this as a motivation to incorporate other heuristics, such as A* or branch-and-bound pruning, so that the resultant search requires a more tractable time to run.
The book is divided into two major parts. Part 1 (five chapters), “Foundations,” introduces the reader to two prototype combinatorial problems, the above-mentioned TSP and SAT problems. The authors chose these problems because of their prominence in the scientific literature, and the ease of problem conceptualization. Part 2 (five chapters), “Applications,” considers classical problems, and applies them to other related problems; there are also independent problems considered, such as scheduling problems, graph coloring, and deoxyribonucleic acid (DNA) code design. For all of these problems, various SLS algorithms are applied and analyzed. Each of the ten chapters in the book closes with two subsections, dedicated, respectively, to “Further Reading and Related Works” and “Summary/Exercises.” The book concludes with an epilogue, glossary, bibliography, and index.
This book can be used either as a textbook for advanced undergraduates, or as an introduction to advanced techniques for graduate students. It can also be considered an encyclopedia of local search techniques. The book is easy to read, the mathematics are easy to follow, and the coverage is extensive. We recommend this book to computer scientists, engineers, and mathematicians alike.
