Local search has been applied successfully to a diverse collection of optimization problems. However, results are scattered throughout the literature. This is the first book that presents a large collection of theoretical results in a consistent manner. It provides the reader with a coherent overview of the achievements obtained so far, and serves as a source of inspiration for the development of novel results in the challenging field of local search.

1. Introduction -- 2. Computational complexity -- 3. Local improvement on discrete structures -- 4. Simulated annealing -- 5. Tabu search -- 6. Genetic algorithms -- 7. Artificial neural networks -- 8. The traveling salesman problem: A case study -- 9. Vehicle routing: Modern heuristics -- 10. Vehicle routing: Handling edge exchanges -- 11. Machine scheduling -- 12. VLSI layout synthesis -- 13. Code design.

Heuristics are strategies using readily accessible, loosely applicable information to control problem solving. Algorithms, for example, are a type of heuristic. By contrast, Metaheuristics are methods used to design Heuristics and may coordinate the usage of several Heuristics toward the formulation of a single method. GRASP (Greedy Randomized Adaptive Search Procedures) is an example of a Metaheuristic. To the layman, heuristics may be thought of as ‘rules of thumb’ but despite its imprecision, heuristics is a very rich field that refers to experience-based techniques for problem-solving, learning, and discovery. Any given solution/heuristic is not guaranteed to be optimal but heuristic methodologies are used to speed up the process of finding satisfactory solutions where optimal solutions are impractical. The introduction to this Handbook provides an overview of the history of Heuristics along with main issues regarding the methodologies covered. This is followed by Chapters containing various examples of local searches, search strategies and Metaheuristics, leading to an analyses of Heuristics and search algorithms. The reference concludes with numerous illustrations of the highly applicable nature and implementation of Heuristics in our daily life. Each chapter of this work includes an abstract/introduction with a short description of the methodology. Key words are also necessary as part of top-matter to each chapter to enable maximum search engine optimization. Next, chapters will include discussion of the adaptation of this methodology to solve a difficult optimization problem, and experiments on a set of representative problems.

In the past three decades, local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization that is attracting ever-increasing attention. Local search is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in reasonable time. Local Search in Combinatorial Optimization covers local search and its variants from both a theoretical and practical point of view, each topic discussed by a leading authority. This book is an important reference and invaluable source of inspiration for students and researchers in discrete mathematics, computer science, operations research, industrial engineering, and management science. In addition to the editors, the contributors are Mihalis Yannakakis, Craig A. Tovey, Jan H. M. Korst, Peter J. M. van Laarhoven, Alain Hertz, Eric Taillard, Dominique de Werra, Heinz Mühlenbein, Carsten Peterson, Bo Söderberg, David S. Johnson, Lyle A. McGeoch, Michel Gendreau, Gilbert Laporte, Jean-Yves Potvin, Gerard A. P. Kindervater, Martin W. P. Savelsbergh, Edward J. Anderson, Celia A. Glass, Chris N. Potts, C. L. Liu, Peichen Pan, Iiro Honkala, and Patric R. J. Östergård.

Wiley-Interscience Series in Discrete Mathematics and Optimization Advisory Editors Ronald L. Graham Jan Karel Lenstra Robert E. Tarjan Discrete Mathematics and Optimization involves the study of finite structures and is one of the fastest growing areas in mathematics today. The level and depth of recent advances in the area and the wide applicability of its evolving techniques point to the rapidity with which the field is moving and presage the ever-increasing interaction between it and computer science. The Series provides a broad coverage of discrete mathematics and optimization, ranging over such fields as combinatorics, graph theory, enumeration, mathematical programming and the analysis of algorithms, and including such topics as Ramsey theory, transversal theory, block designs, finite geometries, Polya theory, graph and matroid algorithms, network flows, polyhedral combinatorics and computational complexity. The Wiley-Interscience Series in Discrete Mathematics and Optimization will be a substantial part of the record in this extraordinary development. Recent title in the Series: Theory and Algorithms for Linear Optimization: An Interior Point Approach C. Roos, T. Terlaky Delft University of Technology, The Netherlands and J.-Ph. Vial University of Geneva, Switzerland Linear Optimization (LO) is one of the most widely taught and fast developing techniques in mathematics, with applications in many areas of science, commerce and industry. The dramatically increased interest in the subject is due mainly to advances in computer technology and to the development of Interior Point Methods (IPM) for LO. This book provides a unified presentation of the field by way of an interior point approach to both the theory of LO and algorithms for LO (design, covergence, complexity and asymptotic behaviour). A common thread throughout the book is the role of strictly complementary solutions, which play a crucial role in the interior point approach and distinguishes the new approach from the classical Simplex-based approach. The approach to LO in this book is new in many aspects. In particular the IPM based development of duality theory is surprisingly elegant. The algorithmic parts of the book contain a complete discussion of many algorithmic variants, including predictor-corrector methods, partial updating, higher order methods and sensitivity and parametric analysis. The comprehensive and up-to-date coverage of the subject, together with the clarity of presentation, ensures that this book will be an invaluable resource for researchers and professionals who wish to develop their understanding of LOs and IPMs . Numerous exercises are provided to help consolidate understanding of the material and more than 45 figures are included to illustrate the characteristics of the algorithms. A general understanding of linear algebra and calculus is assumed and the preliminary chapters provide a self-contained introduction for readers who are unfamiliar with LO methods. These chapters will also be of interest for readers who wish to take a fresh look at the topics. 1997

Over two parts, this book examines the meaning of complexity in the context of systems both social and natural. Chapters cover such topics as the traveling salesman problem, models of opinion dynamics creation, a universal theory for knowledge formation in children, the evaluation of landscape organization and dynamics through information entropy indicators, and studying the performance of wind farms using artificial neural networks. We hope that this book will be useful to an audience interested in the different problems and approaches that are used within the theory of complexity

The satisfiability (SAT) problem is central in mathematical logic, computing theory, and many industrial applications. There has been a strong relationship between the theory, the algorithms and the applications of the SAT problem. This book aims to bring together work by the best theorists, algorithmists, and practitioners working on the sat problem and on industrial applications, as well as to enhance the interaction between the three research groups. The book features the applications of theoretical/algorithmic results to practical problems and presents practical examples for theoretical/algorithmic study. Major topics covered in the book include practical and industial SAT problems and benchmarks, significant case studies and applications of the SAT problem and SAT algorithms, new algorithms and improved techniques for satisfiability testing, specific data structures and implementation details of the SAT algorithms, and the theoretical study of the SAT problem and SAT algorithms.