The Concorde App is a companion to the book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, William Cook, Princeton University Press, 2012.
Given a list of cities and the distance to travel between each pair of them, the traveling salesman problem, or TSP for short, asks for the shortest route to visit each city and to return to the starting point.
In the version of the TSP solved by the Concorde App, the distances are symmetric, that is, the distance to travel from city A to city B is the same as the distance to to travel from B back to A.
The heart of the app is the Concorde TSP solver created by David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. The Concorde code is an exact solver, that is, given an instance of the TSP, it computes the shortest possible tour.
Since 1992, Concorde has set every world record for the largest solved test instances of the TSP. The current record is the solution of an 85,900-city example, computed in 2006, that arose in a computer-chip-design application. On an iPhone 4, Concorde can often solve exactly instances with 1,000 or more cities.
The Concorde code uses the TSPLIB data format, so all travel distances are assumed to be integer valued. In particular, for geometric instances, the travel distances are the straight-line distance rounded to the nearest integer.
The Concorde solver is an implementation of the cutting-plane method for the TSP. At each step, a linear-programming (LP) relaxation of the TSP is solved.
On more difficult instances, Concorde will switch to a branch-and-bound search if the cutting-plane method alone does not appear to be converging rapidly. To save storage space, the Concorde App uses a depth-first-search exploration of the search tree, rather than the best-bound search employed by default in the Concorde code.
At the start of a computation, Concorde runs the Chained Lin-Kernighan heuristic algorithm to obtain a starting tour. The length of this tour is used to evaluate the progress in the cutting-plane method, and to allow for pruning in the branch-and-bound search.
The Concorde app employs the QSopt library to solve LP relaxations that arise in the solution process. QSopt was created by David Applegate, William Cook, Sanjeeb Dash, and Monika Mevenkamp.
Finding the shortest-possible tour is the ultimate target of TSP computation, but in many applications it suffices to find a good approximation to the optimal tour. Many techniques have been developed to fill this need, trading off tour quality for speed. The Tours module displays the solution process used in nine well-known algorithms, described in Chapter 4 of In Pursuit of the Traveling Salesman.
The key to the solution of large instances of the TSP is our ability to discover strong lower bounds on the lengths of possible tours, that is, to find a value B such that we know for certain that no tour can have length less than B. In Concorde we use linear programming to discover such lower bounds.
The drawings created in the Bounds mode provide a means to visualize the LP lower bound resulting from the constraints known as subtour-elimination inequalities. The visualization technique was developed in a research paper by Michael Juenger and William Pulleyblank, published in 1993. It is described in In Pursuit of the Traveling Salesman in Chapter 5, beginning on page 111.
The App will display the geometric bound consisting of a control zone surrounding each city, and moats surrounding some collections of cities. To give a direct sense of the quality of the lower bound, the App also displays a tour found by the Chained Lin-Kernighan heuristic. (The tour may not be the shortest-possible tour.) The text under the drawing gives the lower bound B and the gap between the length of the tour and the value of B. Thus Gap 0.52% means that the tour is guaranteed to be no more that 0.52% longer than a shortest possible tour.
Starting with the locations of the cities, various techniques are available for selecting a set of edges that might be good candidates for use in TSP tours. The Edges module displays several such choices of edges.
The value of k used in the displayed edge sets is selected on the Edges Info screen.
The TSP Art module creates interesting rendering of images as TSP tours. The technique is described in In Pursuit of the Traveling Salesman in Chapter 11, beginning on page 206.
Robert Bosch and Adrianne Herman introduced this idea in work at Oberlin College in 2004, and it was later greatly improved by Craig Kaplan and Robert Bosch.
The Bosch-Herman renderings are based on a grid method for placing points according to the various shades of gray in an image, while the Kaplan-Bosch renderings are based on a weighted version of Lloyd's Algorithm introduced by Adrian Secord.
The TSP App module delivers renderings in the sprit of Bosch-Herman and Kaplan-Bosch, but for much nicer examples please have a look at the work of the masters of the art, Bosch (at Oberlin College) and Kaplan (at the University of Waterloo).
We also include a third rendering style, proposed by Jim Bumgardner (jbum.com) in his Stipple Cam project. Bumgardner writes that his algorithm adopts ideas similar to those used in the Boids project of Craig Reynolds for creating computer models of coordinated animal motion.
The shape of the shortest-possible TSP tour can sometimes vary dramatically with a small change in the location of one of the cities that must be visited by the salesman. To illustrate this point, the TSP Move module allows you to select a city and drag it across the screen while the optimal tour is recomputed on-the-fly. The solution process uses the dynamic-programming algorithm of Bellman-Held-Karp, described in Chapter 9, page 180, of In Pursuit of the Traveling Salesman. The module is only suitable for very small instances, so it is best to select the number of cities to be at most 15.
Many small-scale applications of the TSP involve humans or equipment moving from location to location. Map Router lets you see the shape of such tours drawn on a map. You select city locations by tapping on the map and holding your finger down for about a second. Map Router can work with geometric distances, following the great circle arc between two cities, or with walking or driving distances supplied by Apple's Map Kit Framework.
To compute an optimal tour, we need to know the distance between each pair of cities. This is simple enough for geometric distances, but for walking or driving we need to query the Map Kit servers for the estimated travel time between each pair. This quickly adds up to a large number of queries, so for the walking and driving modes we limit the size of the problems to at most 10 cities. Solving much larger TSP instances is easy with Concorde, but getting the travel information is a bottleneck!