- Membership
- MAA Press
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Princeton University Press

Publication Date:

2007

Number of Pages:

606

Format:

Hardcover

Series:

Princeton Series in Applied Mathematics

Price:

45.00

ISBN:

978-0-691-12993-8

Category:

Monograph

[Reviewed by , on ]

Brian Borchers

03/25/2007

Given a collection of cities and a table of distances between the cities, the traveling salesman problem (TSP) asks for the shortest path that passes through each city exactly once and then returns to its starting point. Although this may seem to be of little practical use, there are many important applications for the TSP and related problems. A classic application is found in the manufacture of printed circuit boards. Holes have to be drilled through the printed circuit board at a large number of designated points. The goal is to find a plan that minimizes the time needed to move the drilling tool around the circuit board to visit each of the holes. The TSP is also of theoretical interest in computer science because it is one of the important class of NP-Hard combinatorial optimization problems.

Because the TSP is an NP-Hard problem, it is unlikely that there will ever be an efficient polynomial time algorithm for its solution. Many researchers and practitioners have focused on efficient heuristics and approximation algorithms rather than attempting to solve the TSP exactly. However, there is also a long history of work on exact methods for the TSP.

An important early result in this direction was the solution in 1954 of a 49 city TSP involving cities from each of the 48 states and the District of Columbia. Dantzig, Fulkerson, and Johnson solved this problem by formulating it as an integer linear programming problem, solving a linear programming relaxation of the problem and strengthening this relaxation of the problem by the addition of constraints called "cuts." In the 1980's, starting with work by Hoffman and Padberg, interest began to grow in cutting plane methods for a variety of combinatorial optimization problems including the TSP. Problem-specific cutting planes were combined with branch and bound techniques for integer linear programming to produce a new approach called "branch and cut."

In 1988, the authors of this book formed a team to work on the TSP using the branch and cut approach together with heuristic methods. Over the course of their study, the authors have made dramatic progress in solving large instances of the TSP, culminating in the development of a branch and cut solver called *Concorde* that has been used to solve some very large TSP instances including one instance with over 85,000 cities. This book is a research monograph summarizing their work on the TSP.

The book begins with chapters on the history of the TSP and its applications. In the second section, the authors describe a large variety of cutting planes for the TSP problem, including recent work that has gone into the *Concorde* solver. This is followed by a discussion of a several important computational issues including the management of LP relaxations and cuts, details of the LP solution process, branching strategies, and heuristic methods for finding good tours. The book concludes with a chapter that looks forward to approaches for solving even larger TSP instances.

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 TSP. This is a very good example of how theoretical research can be translated into software to solve challenging optimization problems that were previously thought to be practically unsolvable.

This book will be of interest to graduate students and researchers working on the TSP. It will also be of interest to the broader group of researchers using branch and cut methods to solve other combinatorial optimization problems. Although the book is very well written, it really isn't appropriate for use as a textbook. Readers looking for an introduction to the techniques used here would be better served by the textbook, *Combinatorial Optimization* , by Cook, Cunningham, Pulleyblank, and Schrijver.

**References:**

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. *Combinatorial Optimization* . John Wiley and Sons, 1997.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.

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 G_{1/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

- Log in to post comments