- ホーム
- > 洋書
- > 英文書
- > Science / Mathematics
Full 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.
Contents
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.
