Calculus of Tolerances in Combinatorial Optimization: Theory and Algorithms

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.