The Traveling Salesman Problem :A Computational Study ( Princeton Series in Applied Mathematics )

Publication subTitle :A Computational Study

Publication series :Princeton Series in Applied Mathematics

Author: Applegate David L.;Bixby Robert E.;Chvátal Vasek  

Publisher: Princeton University Press‎

Publication year: 2011

E-ISBN: 9781400841103

P-ISBN(Paperback): 9780691129938

Subject: O224 mathematical optimization theory

Keyword: 数理科学和化学

Language: ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Description

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.

Chapter

CHAPTER THREE: DANTZIG, FULKERSON, AND JOHNSON

3.1 THE 49-CITY PROBLEM

3.2 THE CUTTING-PLANE METHOD

3.3 PRIMAL APPROACH

CHAPTER FOUR: HISTORY OF TSP COMPUTATION

4.1 BRANCH-AND-BOUND METHOD

4.2 DYNAMIC PROGRAMMING

4.3 GOMORY CUTS

4.4 THE LIN-KERNIGHAN HEURISTIC

4.5 TSP CUTS

4.6 BRANCH-AND-CUT METHOD

4.7 NOTES

CHAPTER FIVE: LP BOUNDS AND CUTTING PLANES

5.1 GRAPHS AND VECTORS

5.2 LINEAR PROGRAMMING

5.3 OUTLINE OF THE CUTTING-PLANE METHOD

5.4 VALID LP BOUNDS

5.5 FACET-INDUCING INEQUALITIES

5.6 THE TEMPLATE PARADIGM FOR FINDING CUTS

5.7 BRANCH-AND-CUT METHOD

5.8 HYPERGRAPH INEQUALITIES

5.9 SAFE SHRINKING

5.10 ALTERNATIVE CALLS TO SEPARATION ROUTINES

CHAPTER SIX: SUBTOUR CUTS AND PQ-TREES

6.1 PARAMETRIC CONNECTIVITY

6.2 SHRINKING HEURISTIC

6.3 SUBTOUR CUTS FROM TOUR INTERVALS

6.4 PADBERG-RINALDI EXACT SEPARATION PROCEDURE

6.5 STORING TIGHT SETS IN PQ-TREES

CHAPTER SEVEN: CUTS FROM BLOSSOMS AND BLOCKS

7.1 FAST BLOSSOMS

7.2 BLOCKS OF…

7.3 EXACT SEPARATION OF BLOSSOMS

7.4 SHRINKING

CHAPTER EIGHT: COMBS FROM CONSECUTIVE ONES

8.1 IMPLEMENTATION OF PHASE 2

8.2 PROOF OF THE CONSECUTIVE ONES THEOREM

CHAPTER NINE: COMBS FROM DOMINOES

9.1 PULLING TEETH FROM PQ-TREES

9.2 NONREPRESENTABLE SOLUTIONS ALSO YIELD CUTS

9.3 DOMINO-PARITY INEQUALITIES

CHAPTER TEN: CUT METAMORPHOSES

10.1 TIGHTEN

10.2 TEETHING

10.3 NADDEF-THIENEL SEPARATION ALGORITHMS

10.4 GLUING

CHAPTER ELEVEN: LOCAL CUTS

11.1 AN OVERVIEW

11.2 MAKING CHOICES OF … AND σ

11.3 REVISIONIST POLICIES

11.4 DOES φ(X*) LIE OUTSIDE THE CONVEX HULL OF T?

11.5 SEPARATING φ(X*) FROM T: THE THREE PHASES

11.6 PHASE 1: FROM T* TO T…

11.7 PHASE 2: FROM T… TO T…

11.8 IMPLEMENTING ORACLE

11.9 PHASE 3: FROM T… TO T

11.10 GENERALIZATIONS

CHAPTER TWELVE: MANAGING THE LINEAR PROGRAMMING PROBLEMS

12.1 THE CORE LP

12.2 CUT STORAGE

12.3 EDGE PRICING

12.4 THE MECHANICS

CHAPTER THIRTEEN: THE LINEAR PROGRAMMING SOLVER

13.1 HISTORY

13.2 THE PRIMAL SIMPLEX ALGORITHM

13.3 THE DUAL SIMPLEX ALGORITHM

13.4 COMPUTATIONAL RESULTS: THE LP TEST SETS

13.5 PRICING

CHAPTER FOURTEEN: BRANCHING

14.1 PREVIOUS WORK

14.2 IMPLEMENTING BRANCH AND CUT

14.3 STRONG BRANCHING

14.4 TENTATIVE BRANCHING

CHAPTER FIFTEEN: TOUR FINDING

15.1 LIN-KERNIGHAN

15.2 FLIPPER ROUTINES

15.3 ENGINEERING LIN-KERNIGHAN

15.4 CHAINED LIN-KERNIGHAN ON TSPLIB INSTANCES

15.5 HELSGAUN’S LKH ALGORITHM

15.6 TOUR MERGING

CHAPTER SIXTEEN: COMPUTATION

16.1 THE CONCORDE CODE

16.2 RANDOM EUCLIDEAN INSTANCES

16.3 THE TSPLIB

16.4 VERY LARGE INSTANCES

16.5 THE WORLD TSP

CHAPTER SEVENTEEN: THE ROAD GOES ON

17.1 CUTTING PLANES

17.2 TOUR HEURISTICS

17.3 DECOMPOSITION METHODS

BIBLIOGRAPHY

INDEX

The users who browse this book also browse