The Traveling Salesman Problem : A Computational Study.
Title:
The Traveling Salesman Problem : A Computational Study.
Author:
Applegate, David L.
ISBN:
9781400841103
Personal Author:
Physical Description:
1 online resource (623 pages)
Series:
Princeton Series in Applied Mathematics
Contents:
COVER -- CONTENTS -- PREFACE -- CHAPTER ONE: THE PROBLEM -- 1.1 TRAVELING SALESMAN -- 1.2 OTHER TRAVELERS -- 1.3 GEOMETRY -- 1.4 HUMAN SOLUTION OF THE TSP -- 1.5 ENGINE OF DISCOVERY -- 1.6 IS THE TSP HARD? -- 1.7 MILESTONES IN TSP COMPUTATION -- 1.8 OUTLINE OF THE BOOK -- CHAPTER TWO: APPLICATIONS -- 2.1 LOGISTICS -- 2.2 GENOME SEQUENCING -- 2.3 SCAN CHAINS -- 2.4 DRILLING PROBLEMS -- 2.5 AIMING TELESCOPES AND X-RAYS -- 2.6 DATA CLUSTERING -- 2.7 VARIOUS APPLICATIONS -- 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.
Abstract:
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.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Subject Term:
Genre:
Electronic Access:
Click to View