About the Concorde iOS App

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.

In Pursuit of the Traveling Salesman

Traveling Salesman Problem

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.


Concorde TSP Solver

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 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.


Cutting-Plane Method

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.


Branch-and-Bound Search

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.


Lin-Kernighan Heuristic

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.


Linear-Programming Solver

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.


Geometric Duality

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 Geometric Duality 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.


TSP Art

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.


Contact Information

We welcome your comments and suggestions. Please contact William Cook at bico@uwaterloo.ca.