David L. Applegate

Traveling Salesman Problem (eBook, ePUB)

A Computational Study

• Format: ePub

Produktbeschreibung

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.

Produktdetails

• Verlag: Princeton University Press
• Seitenzahl: 608
• Erscheinungstermin: 19. September 2011
• Englisch
• ISBN-13: 9781400841103
• Artikelnr.: 38281504

Autorenporträt

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 Chvátal 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.

Inhaltsangabe

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 σ 272 11.3 Revisionist Policies 274 11.4 Does φ(χ*) Lie Outside the
Convex Hull of T ? 275 11.5 Separating φ(χ*) 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