| |
| |
| Preface | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Traveling Salesman | |
| |
| |
| |
| Other Travelers | |
| |
| |
| |
| Geometry | |
| |
| |
| |
| Human Solution of the TSP | |
| |
| |
| |
| Engine of Discovery | |
| |
| |
| |
| Is the TSP Hard? | |
| |
| |
| |
| Milestones in TSP Computation | |
| |
| |
| |
| Outline of the Book | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Logistics | |
| |
| |
| |
| Genome Sequencing | |
| |
| |
| |
| Scan Chains | |
| |
| |
| |
| Drilling Problems | |
| |
| |
| |
| Aiming Telescopes and X-Rays | |
| |
| |
| |
| Data Clustering | |
| |
| |
| |
| Various Applications | |
| |
| |
| |
| Dantzig, Fulkerson, and Johnson | |
| |
| |
| |
| The 49-City Problem | |
| |
| |
| |
| The Cutting-Plane Method | |
| |
| |
| |
| Primal Approach | |
| |
| |
| |
| History of TSP Computation | |
| |
| |
| |
| Branch-and-Bound Method | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| |
| Gomory Cuts | |
| |
| |
| |
| The Lin-Kernighan Heuristic | |
| |
| |
| |
| TSP Cuts | |
| |
| |
| |
| Branch-and-Cut Method | |
| |
| |
| |
| Notes | |
| |
| |
| |
| LP Bounds and Cutting Planes | |
| |
| |
| |
| Graphs and Vectors | |
| |
| |
| |
| Linear Programming | |
| |
| |
| |
| Outline of the Cutting-Plane Method | |
| |
| |
| |
| Valid LP Bounds | |
| |
| |
| |
| Facet-Inducing Inequalities | |
| |
| |
| |
| The Template Paradigm for Finding Cuts | |
| |
| |
| |
| Branch-and-Cut Method | |
| |
| |
| |
| Hypergraph Inequalities | |
| |
| |
| |
| Safe Shrinking | |
| |
| |
| |
| Alternative Calls to Separation Routines | |
| |
| |
| |
| Subtour Cuts and PQ-Trees | |
| |
| |
| |
| Parametric Connectivity | |
| |
| |
| |
| Shrinking Heuristic | |
| |
| |
| |
| Subtour Cuts from Tour Intervals | |
| |
| |
| |
| Padberg-Rinaldi Exact Separation Procedure | |
| |
| |
| |
| Storing Tight Sets in PQ-trees | |
| |
| |
| |
| Cuts from Blossoms and Blocks | |
| |
| |
| |
| Fast Blossoms | |
| |
| |
| |
| Blocks of G | |
| |
| |
| |
| Exact Separation of Blossoms | |
| |
| |
| |
| Shrinking | |
| |
| |
| |
| Combs from Consecutive Ones | |
| |
| |
| |
| Implementation of Phase 2 | |
| |
| |
| |
| Proof of the Consecutive Ones Theorem | |
| |
| |
| |
| Combs from Dominoes | |
| |
| |
| |
| Pulling Teeth from PQ-trees | |
| |
| |
| |
| Nonrepresentable Solutions also Yield Cuts | |
| |
| |
| |
| Domino-Parity Inequalities | |
| |
| |
| |
| Cut Metamorphoses | |
| |
| |
| |
| Tighten | |
| |
| |
| |
| Teething | |
| |
| |
| |
| Naddef-Thienel Separation Algorithms | |
| |
| |
| |
| Gluing | |
| |
| |
| |
| Local Cuts | |
| |
| |
| |
| An Overview | |
| |
| |
| |
| Making Choices of V and sigma; | |
| |
| |
| |
| Revisionist Policies | |
| |
| |
| |
| Does phi;(chi;*) Lie Outside the Convex Hull ofT? | |
| |
| |
| |
| Separating phi;(chi;*) fromT: The Three Phases | |
| |
| |
| |
| PHASE 1: FromT* toT" | |
| |
| |
| |
| PHASE 2: FromT" toT' | |
| |
| |
| |
| Implementing ORACLE | |
| |
| |
| |
| PHASE 3: FromT' toT | |
| |
| |
| |
| Generalizations | |
| |
| |
| |
| Managing the Linear Programming Problems | |
| |
| |
| |
| The Core LP | |
| |
| |
| |
| Cut Storage | |
| |
| |
| |
| Edge Pricing | |
| |
| |
| |
| The Mechanics | |
| |
| |
| |
| The Linear Programming Solver | |
| |
| |
| |
| History | |
| |
| |
| |
| The Primal Simplex Algorithm | |
| |
| |
| |
| The Dual Simplex Algorithm | |
| |
| |
| |
| Computational Results: The LP Test Sets | |
| |
| |
| |
| Pricing | |
| |
| |
| |
| Branching | |
| |
| |
| |
| Previous Work | |
| |
| |
| |
| Implementing Branch and Cut | |
| |
| |
| |
| Strong Branching | |
| |
| |
| |
| Tentative Branching | |
| |
| |
| |
| Tour Finding | |
| |
| |
| |
| Lin-Kernighan | |
| |
| |
| |
| Flipper Routines | |
| |
| |
| |
| Engineering Lin-Kernighan | |
| |
| |
| |
| Chained Lin-Kernighan on TSPLIB Instances | |
| |
| |
| |
| Helsgaun's LKH Algorithm | |
| |
| |
| |
| Tour Merging | |
| |
| |
| |
| Computation | |
| |
| |
| |
| The Concorde Code | |
| |
| |
| |
| Random Euclidean Instances | |
| |
| |
| |
| The TSPLIB | |
| |
| |
| |
| Very Large Instances | |
| |
| |
| |
| The World TSP | |
| |
| |
| |
| The Road Goes On | |
| |
| |
| |
| Cutting Planes | |
| |
| |
| |
| Tour Heuristics | |
| |
| |
| |
| Decomposition Methods | |
| |
| |
| Bibliography | |
| |
| |
| Index | |