Externally indexed torrent

If you are the original uploader, contact staff to have it moved to your account

Textbook in PDF format

In this book we are concerned with problems in combinatorial optimization. Such problems arise in situations where discrete choices must be made, and solving them amounts to finding an optimal solution among a finite or countably infinite number of alternatives. Optimality relates to some cost criterion. Which provides a quantitative measure of the quality of each solution. This area of discrete mathematics is of great practical use and has attracted much attention over the years. For detailed introductions into the field the reader is referred to the books by Lawler [1976], Papadimitriou &amp SteigJitz [1982], Schrijver [1986], and Nemhauser &amp Wolsey [1988]. Useful collections of annotated bibilographics are given by O'hEigeartaigh, Lenstra &amp Rinnooy Kan [ 1985] and Dell'Amico, Maffioli &amp Martello [1997].
Many combinatorial optimization problems are NP-hard see Garey &amp Johnson [1979]. It is generally believed that NP-hard problems cannot be solved to optimality within polynomialty bounded computation times. Consequently, there is much interest in approximation algorithms that can find nearoptimal solutions within reasonable running times. The literature distinguishes between two broad classes of approximation algorithms: constructive and local search methods. This book concentrates on the latter. They are typically instantiations of various general search schemes. but all have the same feature of an underlying neighborhood function, which is used to guide the search for a good solution [Papadimitriou &amp Steiglitz, 1982, Yannakakis, 1990].
The use of local search in combinatorial optimization has a long history that reaches back to the late 1950s and early 1960s, when the first edge-exchange algorithms for the traveling salesman problem (TSP) were introduced: see the work of Hock [1958a,b], Croes [1958], Lin [1965], and Reiter &amp Sherman [1965]. In the subsequent years the scope of local search has been broadened, and the basic concept of an exchange algorithm has been applied with some success to a variety of problems. We mention scheduling [Page, 1965 Nicholson, 1965] and graph partitioning [Kernighan &amp Lin, 1970]. Nicholson [1971] extended the concept of exchange strategies to a more general class of permutation problems, and discussed their application to network layout design, scheduling, vehicle routing, and cutting stock problems. Despite the early successes, local search was not considered a mature technique for a long time. This was mainly because the success could be attributed to its practical usefulness only, and no major conceptual progress was made at that time. The past decade shows a strong renewed interest in the subject, which is due to the following three developments:
- Many variations of local search algorithms have been proposed based on analogies with processes in nature, relating the subject 10 other disciplines such as statistical physics, biological evolution, and neurophysiology. This has generated new algorithms or paradigms. Well-known examples are simulated annealing, genetic algorithms and some variants of neural networks. The analogies are sometimes taken quite far, leading to variants with extravagant names such as the great deluge algorithm of Dueck [1993], the hide and seek game of Belisle, Romeijn &amp Smith [1990], or the roaming ants approach of Colorni, Dorigo &amp Manniezzo [1992].
- Some of the newly proposed local search algorithms have been mathematically modeled. yielding theoretical results on their performance. Probably the best-known example is the modeling of the simulated annealing algorithm by Markov chains [Aarts &amp Karst, 1989a]. Furthermore, Johnson. Papadimitriou &amp Yannakakis [1988] introduced a complexity theory of local search, which provided more theoretical insight, not only into the complexity of local search but also into the combinatorial structure of discrete optimization problems.
- The large increase in computational resources together with the use of sophisticated data structures have made local search algorithms strong competitors within the class of algorithms designed to handle large problem instances. Furthermore, the flexibility and ease of implementation of local search algorithms have led to the successful handling of many соmрleх real-world problems.
Historical Perspective
Formulation and Modeling
Neighborhoods
Analysis and Complexity
Advanced Search Strategies