The Traveling Salesman Problem: A Computational Study

The Traveling Salesman Problem: A Computational Study is a new book by David Applegate, Bob Bixby, Vasek Chvatal, and Bill Cook (published by Princeton University Press) and it is terrific. I was asked by OR Letters to provide a review, which I have done. I won’t spoil the review for the journal, but here is my final paragraph(before editing):

At one level, this book may appear to be about a particular computer code for a particular combinatorial optimization problem, but I believe it is far more. Much of the research we do is incremental, involving a small step on a subproblem of a subproblem of a subproblem. Rarely do we step back and see the big picture. This book is, fundamentally, about the big picture. The authors, in their computer code and in their writings, have taken the best from the extensive literature and shown how we as a field have moved forward. At this point, algorithms, implementation, and computing have advanced sufficiently that almost any instance of practical interest can be solved to optimality with sufficient, but reasonable, computing resources. The incremental improvements add up to a tremendous success. By bringing together the best work from a wide array of researchers, describing it in a book, and implementing it in a code, the authors show how research in computational combinatorial optimization should be done.

I really like the book. And I particularly appreciate the publisher for putting it out at a reasonable price: under $50.

4 thoughts on “The Traveling Salesman Problem: A Computational Study”

  1. Yes! I was lucky enough to review this for MAA Reviews. I gave it my strongest recommendation.

    I’d disagree slightly with your characterization of “bringing together the best work from a wide array of researchers.” The recent work described in the book is very much research performed by the authors, but then they have been at the forefront in this area for some time.

  2. I think the rest of the review makes it clear that I include the authors as part of the array of researchers. One aspect that I think they do a good job of is reviewing and summarizing the work of others. But you are right that there is a tremendous amount of original research in the book, and I will be sure my review points that out.

Leave a Reply

Your email address will not be published. Required fields are marked *