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 authors of this book are the same pioneers who for nearly two decades have led the investigation into the traveling salesman problem. They have derived solutions to almost eighty-six thousand cities, yet a general solution to the problem has yet to be discovered. Here they describe the method and computer code they used to solve a broad range of large-scale problems, and along the way they demonstrate the interplay of applied mathematics with increasingly powerful computing platforms. They also give the fascinating history of the problem--how it developed, and why it continues to intrigue us.

Table of Contents:
Preface xi Chapter 1: The Problem 1 1.1 Traveling Salesman 1 1.2 Other Travelers 5 1.3 Geometry 15 1.4 Human Solution of the TSP 31 1.5 Engine of Discovery 40 1.6 Is the TSP Hard? 44 1.7 Milestones in TSP Computation 50 1.8 Outline of the Book 56 Chapter 2: Applications 59 2.1 Logistics 59 2.2 Genome Sequencing 63 2.3 Scan Chains 67 2.4 Drilling Problems 69 2.5 Aiming Telescopes and X-Rays 75 2.6 Data Clustering 77 2.7 Various Applications 78 Chapter 3: Dantzig, Fulkerson, and Johnson 81 3.1 The 49-City Problem 81 3.2 The Cutting-Plane Method 89 3.3 Primal Approach 91 Chapter 4: History of TSP Computation 93 4.1 Branch-and-Bound Method 94 4.2 Dynamic Programming 101 4.3 Gomory Cuts 102 4.4 The Lin-Kernighan Heuristic 103 4.5 TSP Cuts 106 4.6 Branch-and-Cut Method 117 4.7 Notes 125 Chapter 5: LP Bounds and Cutting Planes 129 5.1 Graphs and Vectors 129 5.2 Linear Programming 131 5.3 Outline of the Cutting-Plane Method 137 5.4 Valid LP Bounds 139 5.5 Facet-Inducing Inequalities 142 5.6 The Template Paradigm for Finding Cuts 145 5.7 Branch-and-Cut Method 148 5.8 Hypergraph Inequalities 151 5.9 Safe Shrinking 153 5.10 Alternative Calls to Separation Routines 156 Chapter 6: Subtour Cuts and PQ-Trees 159 6.1 Parametric Connectivity 159 6.2 Shrinking Heuristic 164 6.3 Subtour Cuts from Tour Intervals 164 6.4 Padberg-Rinaldi Exact Separation Procedure 170 6.5 Storing Tight Sets in PQ-trees 173 Chapter 7: Cuts from Blossoms and Blocks 185 7.1 Fast Blossoms 185 7.2 Blocks of G1/2 187 7.3 Exact Separation of Blossoms 191 7.4 Shrinking 194 Chapter 8: Combs from Consecutive Ones 199 8.1 Implementation of Phase 2 202 8.2 Proof of the Consecutive Ones Theorem 210 Chapter 9: Combs from Dominoes 221 9.1 Pulling Teeth from PQ-trees 223 9.2 Nonrepresentable Solutions also Yield Cuts 229 9.3 Domino-Parity Inequalities 231 Chapter 10: Cut Metamorphoses 241 10.1 Tighten 243 10.2 Teething 248 10.3 Naddef-Thienel Separation Algorithms 256 10.4 Gluing 261 Chapter 11: Local Cuts 271 11.1 An Overview 271 11.2 Making Choices of V and sigma 272 11.3 Revisionist Policies 274 11.4 Does phi(chi*) Lie Outside the Convex Hull of T ? 275 11.5 Separating phi(chi*) from T : The Three Phases 289 11.6 PHASE 1: From T* to T" 291 11.7 PHASE 2: From T" to T' 315 11.8 Implementing ORACLE 326 11.9 PHASE 3: From T' to T 329 11.10 Generalizations 339 Chapter 12: Managing the Linear Programming Problems 345 12.1 The Core LP 345 12.2 Cut Storage 354 12.3 Edge Pricing 362 12.4 The Mechanics 367 Chapter 13: The Linear Programming Solver 373 13.1 History 373 13.2 The Primal Simplex Algorithm 378 13.3 The Dual Simplex Algorithm 384 13.4 Computational Results: The LP Test Sets 390 13.5 Pricing 404 Chapter 14: Branching 411 14.1 Previous Work 411 14.2 Implementing Branch and Cut 413 14.3 Strong Branching 415 14.4 Tentative Branching 417 Chapter 15: Tour Finding 425 15.1 Lin-Kernighan 425 15.2 Flipper Routines 436 15.3 Engineering Lin-Kernighan 449 15.4 Chained Lin-Kernighan on TSPLIB Instances 458 15.5 Helsgaun's LKH Algorithm 466 15.6 Tour Merging 469 Chapter 16: Computation 489 16.1 The Concorde Code 489 16.2 Random Euclidean Instances 493 16.3 The TSPLIB 500 16.4 Very Large Instances 506 16.5 The World TSP 524 Chapter 17: The Road Goes On 531 17.1 Cutting Planes 531 17.2 Tour Heuristics 534 17.3 Decomposition Methods 539 Bibliography 541 Index 583