Imagine you have a map with a collection of cities and a table showing the distances between each city. Now, picture trying to find the shortest path that passes through every city once and then returns to the starting point. That’s the traveling salesman problem (TSP) in a nutshell.
While it may not seem like something you’d encounter in everyday life, the TSP actually has many important applications. For example, imagine you’re manufacturing printed circuit boards and need to drill holes at specific points. You want to find the most efficient plan to move the drilling tool around the board, visiting each hole in the least amount of time. The TSP also holds theoretical interest in computer science as one of the most important NP-Hard optimization problems.
However, solving the TSP efficiently is a challenge. It’s an NP-Hard problem, which means finding a polynomial time algorithm for its solution is highly unlikely. Instead, researchers and practitioners have focused on developing efficient heuristics and approximation algorithms to tackle the TSP. But that doesn’t mean there haven’t been advancements in exact methods for solving the TSP.
Back in 1954, a major breakthrough was achieved in solving a TSP with 49 cities, spanning all 48 states and the District of Columbia. Dantzig, Fulkerson, and Johnson formulated the problem as an integer linear programming problem and solved it by adding constraints called “cuts” to strengthen the linear programming relaxation. Fast forward to the 1980s, cutting-edge methods like cutting plane methods, which combine problem-specific cutting planes with branch and bound techniques for integer linear programming, started gaining attention for solving TSP and other combinatorial optimization problems.
In 1988, the authors of The Traveling Salesman Problem: A Computational Study formed a team and embarked on their own TSP journey, using the branch and cut approach along with heuristic methods. Their hard work paid off, as they made significant progress in solving large-scale TSP instances, leading to the development of their branch and cut solver, Concorde. Concorde has successfully tackled TSP instances with over 85,000 cities. The Traveling Salesman Problem: A Computational Study serves as a research monograph, summarizing their extensive work on the TSP.
The Traveling Salesman Problem: A Computational Study starts off by diving into the history of the TSP and its real-world applications. Next, the authors delve into various cutting planes for the TSP, including their latest contributions to the Concorde solver. They also tackle important computational issues, such as managing LP relaxations and cuts, the LP solution process, branching strategies, and heuristic methods for finding optimal tours. Finally, the book concludes by exploring future approaches to solving even larger TSP instances.
The authors do an outstanding job of explaining how they developed new techniques to overcome the challenges posed by increasingly larger TSP instances. This book serves as a brilliant example of how theoretical research can be translated into practical software that tackles complex optimization problems once thought to be unsolvable.
Graduate students and researchers working on the TSP will find this book incredibly valuable. It’s also of interest to researchers using branch and cut methods to solve other combinatorial optimization problems. However, while the book is well-written, it’s not ideal for use as a textbook. Those seeking an introduction to the techniques used in The Traveling Salesman Problem: A Computational Study would be better served by the textbook “Combinatorial Optimization” by Cook, Cunningham, Pulleyblank, and Schrijver.
