Applegate / Bixby / Chvátal | The Traveling Salesman Problem | E-Book | sack.de
E-Book

E-Book, Englisch, Band 17, 608 Seiten

Reihe: Princeton Series in Applied Mathematics

Applegate / Bixby / Chvátal The Traveling Salesman Problem

A Computational Study
Course Book
ISBN: 978-1-4008-4110-3
Verlag: De Gruyter
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

A Computational Study

E-Book, Englisch, Band 17, 608 Seiten

Reihe: Princeton Series in Applied Mathematics

ISBN: 978-1-4008-4110-3
Verlag: De Gruyter
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)



No detailed description available for "The Traveling Salesman Problem".

Applegate / Bixby / Chvátal The Traveling Salesman Problem jetzt bestellen!

Weitere Infos & Material


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


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.



Ihre Fragen, Wünsche oder Anmerkungen
Vorname*
Nachname*
Ihre E-Mail-Adresse*
Kundennr.
Ihre Nachricht*
Lediglich mit * gekennzeichnete Felder sind Pflichtfelder.
Wenn Sie die im Kontaktformular eingegebenen Daten durch Klick auf den nachfolgenden Button übersenden, erklären Sie sich damit einverstanden, dass wir Ihr Angaben für die Beantwortung Ihrer Anfrage verwenden. Selbstverständlich werden Ihre Daten vertraulich behandelt und nicht an Dritte weitergegeben. Sie können der Verwendung Ihrer Daten jederzeit widersprechen. Das Datenhandling bei Sack Fachmedien erklären wir Ihnen in unserer Datenschutzerklärung.