Calculus of Tolerances in Combinatorial Optimization 2016
Theory and Algorithms
Springer (Publisher)
Published on 5. September 2016
Book
Hardback
382 pages
978-1-4939-4006-6 (ISBN)
Description
This book focuses on the theory of calculus of tolerances and its applications to heuristics and exact algorithms for combinatorial optimization problems (COPs). A tolerance is the maximum perturbation of a single element value within an optimal solution while all other input data is unchanged. This exposition specifically discusses tolerances for describing the structure and relationships among optimal solutions to combinatorial optimization problems. Applications of tolerances for solving the symmetric, asymmetric, second order traveling salesman problems, maximum weight independent set problem, and different classes of vehicle routing problems are discussed in detail. Numerous insightful examples and remarks help the reader master theoretical results and understand the framework of tolerance based algorithms and underlying concepts. Aimed toward designers of efficient algorithms, this book would benefit graduate students, researchers and engineers in operations research, computer science, applied mathematics, bioinformatics, artificial intelligence, and machine learning.
More details
Series
Edition
2016 ed.
Language
English
Place of publication
New York
United States
Target group
College/higher education
Professional and scholarly
Illustrations
40 s/w Abbildungen, 35 farbige Abbildungen
40 black & white illustrations, 35 colour illustrations, biography
Dimensions
Height: 235 mm
Width: 155 mm
ISBN-13
978-1-4939-4006-6 (9781493940066)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Content
1.Introduction.- 2. Notations and Definitions.- 3. The Theory of Tolerances.- 4. Heuristics for the Asymmetric Traveling Salesman Problem.- 5. Heuristics for the Symmetric Traveling Salesman Problem.- 6. Heuristics and Exact Algorithms for the Traveling Salesman Problem of Second Order.- 7. Tolerance Based Branch and Bound for the Asymmetric Traveling Salesman Problem.- 8. The Performance of Branch and Bound for the Asymmetric Traveling Salesman Problem.- 9. Tolerance Based Branch and Bound Algorithms for Asymmetric Vehicle Routing Problems.- 10. The computation of large sets of upper and lower tolerances.- 11. Global Tolerances in Combinatorial Optimization.- Index.