Chvatal V. The Traveling Salesman Problem. A Comput. Study 2011

Textbook in PDF format

This book presents the latest findings on one of the most intensely investigated subjects in computational mathematics--the traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience. The autho.
Frontmatter
Preface
The Problem
Applications
Dantzig, Fulkerson, and Johnson
History of TSP Computation
LP Bounds and Cutting Planes
Subtour Cuts and PQ-Trees
Cuts from Blossoms and Blocks
Combs from Consecutive Ones
Combs from Dominoes
Cut Metamorphoses
Local Cuts
Managing the Linear Programming Problems
The Linear Programming Solver Chapter 14. Branching
Branching
Tour Finding
Computation
The Road Goes On
Bibliography
Index