Traveling Salesman Problem

David L. Applegate is a researcher at AT&T Labs. Robert E. Bixby is Research Professor of Management and Noah Harding Professor of Computational and Applied Mathematics at Rice University. Vasek Chvatal is Canada Research Chair in Combinatorial Optimization at Concordia University. William J. Cook is Chandler Family Chair in Industrial and Systems Engineering at the Georgia Institute of Technology.

Winner of the 2007 Lanchester Prize, Informs "The authors have done a wonderful job of explaining how they developed new techniques in response to the challenges posed by ever larger instances of the Traveling Salesman Problem."--MAA Online "By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done."--Michael Trick, Operations Research Letters "The book is certainly a must for every researcher in practical TSP-computation."--Ulrich Faigle, Mathematical Reviews "It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art."--Stefan Nickel, Zentralblatt MATH "[T]the text read[s] more like a best-seller than a tome of mathematics... The resulting book provides not only a map for understanding TSP computation, but should be the starting point for anyone interested in launching a computational assault on any combinatorial optimization problem."--Jan Karel Lenstra, SIAM Review "By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done."--Michael Trick, ScienceDirect "[T]he book provides a comprehensive treatment of the traveling salesman problem and I highly recommend it not only to specialists in the area but to anyone interested in combinatorial optimization."--EMS Newsletter

• 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