- Hardcover: 606 pages
- Publisher: Princeton University Press (15 Jan 2007)
- Language English
- ISBN-10: 0691129932
- ISBN-13: 978-0691129938
- Product Dimensions: 24 x 16.3 x 4.3 cm
- Amazon Bestsellers Rank: 595,523 in Books (See Top 100 in Books)
- See Complete Table of Contents
The Traveling Salesman Problem
and over one million other books are available for Amazon Kindle .
Learn more
| |||||||||||||||
Did you know you can trade in your old books for an Amazon.co.uk Gift Card to spend on the things you want? Plus, get an extra £5 Gift Certificate when you trade in books worth £10 or more before June 30, 2012. Visit the Books Trade-In Store for more details. |
Product details |
More About the Author
Product Description
Review
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
[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
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
[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
Product 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.
Inside This Book
(Learn More)
First Sentence
Given a set of cities along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cities and returning to the starting point. Read the first page Browse Sample Pages
Front Cover | Copyright | Table of Contents | Excerpt | Index
Given a set of cities along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cities and returning to the starting point. Read the first page Browse Sample Pages
Front Cover | Copyright | Table of Contents | Excerpt | Index
Tag this product(What's this?)Think of a tag as a keyword or label you consider is strongly related to this product.
Tags will help all customers organise and find favourite items. |
What Other Items Do Customers Buy After Viewing This Item?
Customer Reviews
There are no customer reviews yet on Amazon.co.uk.
5 star
4 star
3 star
2 star
1 star
Most Helpful Customer Reviews on Amazon.com (beta)
Amazon.com:
3 reviews
11 of 11 people found the following review helpful
Twenty years in the making
14 July 2007
Format:Hardcover
The coauthors have been working at solving large scale traveling saleman problem instances for more than 20 years. This book, along with the publicly available Concorde code, is the culmination of that twenty years of work.
The first four chapters of the book (130 pages or so) are an extremely readable description of the use and history of the traveling salesman problem. For our field, the traveling salesman problem has been an exemplar of a hard combinatorial problem, commonly used to test new ideas in problem solving. It is no coincidence that the first papers on simulated annealing, DNA computing, and other approaches for combinatorial problems describe their methods in the context of the TSP: it is the most well known of all the problems in operations research.
The authors' primary emphasis is on computation: how can optimal tours be found? The history of TSP computation is very much the history of computational combinatorial optimization. From the fundamental work of Dantzig, Fulkerson, and Johnson in solving the famous 42-city example, through Held and Karp's relaxations andLin-Kernighan's improvement heuristics, to modern-day branch-and-cut, the TSP has been at the forefront of computational methods in our field. The description of this history is outstanding, and appropriately nontechnical, suitable for reading by beginners in operations research.
The main part of the book is on the computational approaches needed to solve large TSPs. This part is well-written, though beyond a beginner level. Despite that, it has broad interest in the way it melds computational issues (like data structures and heuristic ordering) with the theory.
At the end, this book is an exemplar for how to do research in computational operations research. While not aimed at the non-specialist, it is perfectly readable by those who have gone through an introduction in optimization or operations research.
The first four chapters of the book (130 pages or so) are an extremely readable description of the use and history of the traveling salesman problem. For our field, the traveling salesman problem has been an exemplar of a hard combinatorial problem, commonly used to test new ideas in problem solving. It is no coincidence that the first papers on simulated annealing, DNA computing, and other approaches for combinatorial problems describe their methods in the context of the TSP: it is the most well known of all the problems in operations research.
The authors' primary emphasis is on computation: how can optimal tours be found? The history of TSP computation is very much the history of computational combinatorial optimization. From the fundamental work of Dantzig, Fulkerson, and Johnson in solving the famous 42-city example, through Held and Karp's relaxations andLin-Kernighan's improvement heuristics, to modern-day branch-and-cut, the TSP has been at the forefront of computational methods in our field. The description of this history is outstanding, and appropriately nontechnical, suitable for reading by beginners in operations research.
The main part of the book is on the computational approaches needed to solve large TSPs. This part is well-written, though beyond a beginner level. Despite that, it has broad interest in the way it melds computational issues (like data structures and heuristic ordering) with the theory.
At the end, this book is an exemplar for how to do research in computational operations research. While not aimed at the non-specialist, it is perfectly readable by those who have gone through an introduction in optimization or operations research.
4 of 4 people found the following review helpful
An Excellent Introduction to Algorithm Design for Combinatorial Optimisation
15 Oct 2008
Format:Hardcover
The latest book by Applegate, Bixby, Chvátal, and Cook provides an excellent survey of methods that kick-started the "engine of discovery in applied mathematics", known as the Travelling Salesman Problem (TSP). In more than 600 pages, the authors present a survey of methods used in their present-best TSP solver Concorde, almost to the exclusion of any other content. Chapters 1-4 describe the TSP and Chapters 5-6 provide a brief introduction to solving the TSP by using the branch and cut method. At the heart of the book are then Chapters 7-11, which survey various classes of cuts, in some cases first proposed by the authors themselves. Chapter 7 surveys cuts from blossoms and blocks, Chapter 8 presents cuts from combs and consecutive ones, and Chapter 9 introduces cuts from dominoes. Chapters 11 and 12 then describe in yet more detail separation and metamorphoses of strong valid inequalities. Other variants of the problem, such as the asymmetric TSP, and other solution approaches, including metaheuristics and approximation algorithms, are mentioned only in the passing. They are, however, well-covered elsewhere (Gutin & Punnen, 2002), and the seemingly narrow focus consequently enables the authors to provide an outstandingly in-depth treatment.
I cannot be stressed enough how much the treatment benefits from authors' extensive experience with development of Concorde (http://www.tsp.gatech.edu/). In many textbooks on combinatorial optimisation, primal heuristics are mentioned only in passing and cuts are presented in the very mathematical style of definition - proof of validity - proof of dimensionality. Not here. Chapter 6-11 suggest separation routines, exact or heuristic, alongside the description of strong valid inequalities, Chapter 12 is devoted to management of cuts and instances of linear programming, Chapter 13 describes pricing routines for column generation, and last but not least, Chapter 15 is devoted to primal (tour-finding) heuristics. "Implementation details", such as the choice of suitable data structures and trade-offs between heuristic and exact separation, are thoroughly discussed. This makes the book a wonderful introduction to the design of branch-and-cut/price in general.
Although narrow in scope, the book can be recommended to a surprisingly wide audience -- most likely to any researcher working in combinatorial optimisation, and anyone else with a keen interest in algorithm design for combinatorial optimisation.
For the full review, see DOI [...].
I cannot be stressed enough how much the treatment benefits from authors' extensive experience with development of Concorde (http://www.tsp.gatech.edu/). In many textbooks on combinatorial optimisation, primal heuristics are mentioned only in passing and cuts are presented in the very mathematical style of definition - proof of validity - proof of dimensionality. Not here. Chapter 6-11 suggest separation routines, exact or heuristic, alongside the description of strong valid inequalities, Chapter 12 is devoted to management of cuts and instances of linear programming, Chapter 13 describes pricing routines for column generation, and last but not least, Chapter 15 is devoted to primal (tour-finding) heuristics. "Implementation details", such as the choice of suitable data structures and trade-offs between heuristic and exact separation, are thoroughly discussed. This makes the book a wonderful introduction to the design of branch-and-cut/price in general.
Although narrow in scope, the book can be recommended to a surprisingly wide audience -- most likely to any researcher working in combinatorial optimisation, and anyone else with a keen interest in algorithm design for combinatorial optimisation.
For the full review, see DOI [...].
THE MOST COMPLETE WORK ON TSP
24 April 2012
Format:Hardcover|Amazon Verified Purchase
This book covers almost all techniques and approaches to solve the TSP. The authors were the greater contributors to the construction of exact and heuristic solutions we know about. The salesman problem still is challenger to the students and still has a strong appeal. We can look around to other interesting problems, but sometimes we look again to TSP to check for improvements. The TSP is one of the simplest ones to enunciate but it is NP hard.
Probably it is hard also to find another book as complete like this one.
Probably it is hard also to find another book as complete like this one.
Were these reviews helpful?
Let us know
Listmania!
Look for similar items by category
Look for similar items by subject
Feedback
- Would you like to update product info or give feedback on images?
- I am the Author, and I want to comment on my book.
- I am the Publisher, and I want to comment on this book.
|
