The traveling salesman problem : a computational study / David L. Applegate ... [et al.].

Format:

Book

Author/Creator:

Applegate, David L.

Bixby, Robert E., Author.

Chvátal, Vašek, Author.

Series:

Princeton series in applied mathematics.

Princeton series in applied mathematics

Language:

English

Subjects (All):

Traveling salesman problem.

Physical Description:

1 online resource (606 p.)

Edition:

Course Book

Place of Publication:

Princeton : Princeton University Press, c2006.

Language Note:

English

Summary:

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.

Contents:

Front matter

Contents

Preface

Chapter 1. The Problem

Chapter 2. Applications

Chapter 3. Dantzig, Fulkerson, and Johnson

Chapter 4. History of TSP Computation

Chapter 5. LP Bounds and Cutting Planes

Chapter 6. Subtour Cuts and PQ-Trees

Chapter 7. Cuts from Blossoms and Blocks

Chapter 8. Combs from Consecutive Ones

Chapter 9. Combs from Dominoes

Chapter 10. Cut Metamorphoses

Chapter 11. Local Cuts

Chapter 12. Managing the Linear Programming Problems

Chapter 13. The Linear Programming Solver Chapter 14. Branching

Chapter 14. Branching

Chapter 15. Tour Finding

Chapter 16. Computation

Chapter 17. The Road Goes On

Bibliography

Index

Notes:

"A Princeton University Press e-book."--Cover.

Includes bibliographical references (p. [541]-581) and index.

ISBN:

9786613256119

9781283256117

1283256118

9781400841103

1400841100

OCLC:

749265038