Theoretical aspects of local search. (Q859710): Difference between revisions

For 50 years, local search methods have been very successfully applied to large scale combinatorial optimization problems arising in real world situations. While the vast majority of the literature reports on experimental results with local search strategies applied to specific problems, this book focuses on theoretical aspects, in mainly three areas: -- performance guarantees, -- time complexity, -- asymptotic convergence. Throughout the book, the authors use exemplary problems such as the TSP and scheduling problems for which they prove results relating to the above topics. In Chapter 1 the authors give the fundamental definitions to positions local search within combinatorial optimization. In Chapter 2 examples of local search algorithms are given, starting, one might say of course, with \(k\)-change for the travelling salesman problem (TSP). The other example problems are machine scheduling, the Steiner Tree Problem on graphs, graph coloring and stable configuration in Hopfield networks. In Chapter 3 the authors discuss indirect representation of solutions, i.e. by features such that for any value of that feature a best solution with that value is identifiable in polynomial time. Some examples from scheduling are given. In Chapter 4 properties of neighborhood functions are discussed, in particular the diameter and connectivity of neighborhood graphs for TSP and scheduling. In Chapters 5 and 6 the authors proceed to the main results in the first two areas mentioned above. Chapter 5 addresses the performance guarantees for local search algorithms, i.e. worst case analysis. First, the authors discuss exact neighborhood functions, (for which every local optimum is global, e.g. conditions for exactness of \(k\)-change for TSP) then performance ratios (again for \(k\)-change for TSP but also move and swap in scheduling) followed by non-approximability results, and how for certain problems neighborhood functions lead to polynomial time algorithms. In Chapter 6, the complexity of local search is studied. The class PLS and the notion of PLS completeness are defined and PLS-completeness results are proved. Next, the time complexity of iterative improvement algorithms is investigated. Again, results for TSP and scheduling are proved. Finally, in Chapter 7 the authors present the basics of metaheuristics Simulated Annealing, Tabu Search, random restart GRASP and iterated local search. In Chapter 8 they provide the necessary background on Markov chains to be able to prove asymptotic convergence of Simulate Annealing. The book is complemented by appendices on graph theory and complexity theory that cover material used in the book. Another appendix contains a list of PLS-complete problems. Each chapter is concluded with bibliographical notes for further reading and exercises. Throughout the authors avoid excessive and unnecessary formalism which leads to a style that makes even the more technical proofs quite easily readable. The book is suitable for a postgraduate course on the theory of local search. With its collection of results concerning the theoretical aspects of local search it is a most welcome addition to the literature on the topic.