The Traveling Salesman Problem: A Computational Study

Valutazione media 4,14
( su 7 valutazioni fornite da GoodReads )
 
9780691129938: The Traveling Salesman Problem: A Computational Study

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.

Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.

Recensione:

Winner of the 2007 Lanchester Prize, Informs

"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 Traveling Salesman Problem." --MAA Online

"By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done." --Michael Trick, Operations Research Letters

"The book is certainly a must for every researcher in practical TSP-computation." --Ulrich Faigle, Mathematical Reviews

"It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art." --Stefan Nickel, Zentralblatt MATH

"[T]the text read[s] more like a best-seller than a tome of mathematics. . . . The resulting book provides not only a map for understanding TSP computation, but should be the starting point for anyone interested in launching a computational assault on any combinatorial optimization problem." --Jan Karel Lenstra, SIAM Review

"By bringing together the best work from a wide array of researchers, advancing the field where needed, describing their findings in a book, and implementing everything in an extremely well-written computer program, the authors show how research in computational combinatorial optimization should be done." --Michael Trick, ScienceDirect

"[T]he book provides a comprehensive treatment of the traveling salesman problem and I highly recommend it not only to specialists in the area but to anyone interested in combinatorial optimization." --EMS Newsletter

Contenuti:

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

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

Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.

I migliori risultati di ricerca su AbeBooks

1.

David L. Applegate
Editore: Princeton University Press (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Quantità: 6
Da
Books2Anywhere
(Fairford, GLOS, Regno Unito)
Valutazione libreria
[?]

Descrizione libro Princeton University Press, 2007. HRD. Condizione libro: New. New Book. Shipped from UK in 4 to 14 days. Established seller since 2000. Codice libro della libreria WP-9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 63,07
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 10,40
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi

2.

David L. Applegate, Robert E. Bixby, Vasek Chvatal
Editore: Princeton University Press, United States (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Da
The Book Depository
(London, Regno Unito)
Valutazione libreria
[?]

Descrizione libro Princeton University Press, United States, 2007. Hardback. Condizione libro: New. 234 x 162 mm. Language: English . Brand New Book. 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. Codice libro della libreria AAZ9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 77,10
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi

3.

David L. Applegate, Robert E. Bixby, Vasek Chvatal
Editore: Princeton University Press, United States (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Da
The Book Depository US
(London, Regno Unito)
Valutazione libreria
[?]

Descrizione libro Princeton University Press, United States, 2007. Hardback. Condizione libro: New. 234 x 162 mm. Language: English . Brand New Book. 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. Codice libro della libreria AAZ9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 77,32
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi

4.

Applegate, David L.; Bixby, Robert E.; Chvatal, Vasek; Cook, William J.
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Quantità: 1
Da
Speedy Hen LLC
(Sunrise, FL, U.S.A.)
Valutazione libreria
[?]

Descrizione libro Condizione libro: New. Bookseller Inventory # ST0691129932. Codice libro della libreria ST0691129932

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 79,22
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi

5.

David L. Applegate, Robert E. Bixby, Vasek Chvatal
Editore: Princeton University Press 2007-01-15, New Jersey (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 10
Da
Blackwell's
(Oxford, OX, Regno Unito)
Valutazione libreria
[?]

Descrizione libro Princeton University Press 2007-01-15, New Jersey, 2007. hardback. Condizione libro: New. Codice libro della libreria 9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 76,87
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 5,20
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi

6.

Applegate, David L.; Bixby, Robert E.; Chvatal, Vasek; Cook, William J.
Editore: Princeton University Press (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Valutazione libreria
[?]

Descrizione libro Princeton University Press, 2007. Condizione libro: New. 2007. 2nd Printing. Hardcover. Presents the findings on one of the most intensely investigated subjects in computational mathematics - the travelling salesman problem. This book describes the method and computer code used to solve a range of large-scale problems, and demonstrates the interplay of applied mathematics with increasingly powerful computing platforms. Series: Princeton Series in Applied Mathematics. Num Pages: 608 pages, 200 line illus. BIC Classification: PBW; UYA. Category: (P) Professional & Vocational; (U) Tertiary Education (US: College). Dimension: 241 x 165 x 43. Weight in Grams: 1056. . . . . . . Codice libro della libreria V9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 87,59
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
Da: Irlanda a: U.S.A.
Destinazione, tempi e costi

7.

David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Da
Ria Christie Collections
(Uxbridge, Regno Unito)
Valutazione libreria
[?]

Descrizione libro Hardback. Condizione libro: New. Not Signed; 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 rou. book. Codice libro della libreria ria9780691129938_rkm

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 86,25
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 3,86
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi

8.

Applegate, David L.; Bixby, Robert E.; Chvatal, Vasek; Cook, William J.
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Quantità: 1
Da
BWB
(Valley Stream, NY, U.S.A.)
Valutazione libreria
[?]

Descrizione libro Condizione libro: New. Depending on your location, this item may ship from the US or UK. Codice libro della libreria 97806911299380000000

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 93,23
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi

9.

Applegate, David L.; Bixby, Robert E.; Chvatal, Vasek; Cook, William J.
Editore: Princeton University Press
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Da
Kennys Bookstore
(Olney, MD, U.S.A.)
Valutazione libreria
[?]

Descrizione libro Princeton University Press. Condizione libro: New. 2007. 2nd Printing. Hardcover. Presents the findings on one of the most intensely investigated subjects in computational mathematics - the travelling salesman problem. This book describes the method and computer code used to solve a range of large-scale problems, and demonstrates the interplay of applied mathematics with increasingly powerful computing platforms. Series: Princeton Series in Applied Mathematics. Num Pages: 608 pages, 200 line illus. BIC Classification: PBW; UYA. Category: (P) Professional & Vocational; (U) Tertiary Education (US: College). Dimension: 241 x 165 x 43. Weight in Grams: 1056. . . . . . Books ship from the US and Ireland. Codice libro della libreria V9780691129938

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 93,57
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi

10.

David L. Applegate; Robert E. Bixby; Vasek Chvatal; William J. Cook
Editore: Princeton University Press (2007)
ISBN 10: 0691129932 ISBN 13: 9780691129938
Nuovi Rilegato Quantità: 1
Da
Ergodebooks
(RICHMOND, TX, U.S.A.)
Valutazione libreria
[?]

Descrizione libro Princeton University Press, 2007. Hardcover. Condizione libro: New. Codice libro della libreria SONG0691129932

Maggiori informazioni su questa libreria | Fare una domanda alla libreria

Compra nuovo
EUR 91,36
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 3,70
In U.S.A.
Destinazione, tempi e costi

Vedi altre copie di questo libro

Vedi tutti i risultati per questo libro