William Cook and the TSP @ Georgia Tech

Given my new found interest in the Travelling Salesman Problem, I thought it prudent to start reading up on the problem from the perspective of the prominent resources on the web. An excellent starting point is William Cook's Travelling Salesman Problem page, hosted at Georgia Tech.

I was familiar with Cook and his resource given its high ranking in Google searches (American Spelling), mention TSP Wikipedia article, and my colleagues mention of Cook, et al's CONCORDE TSP Solver any time I talked about the general problem. Cook's page is detailed in its coverage of the problem and his involvement with solving specific instances. I thought I would provide a general overview of the offerings of his TSP portal.

An overview of the general problem is provided that includes a set of links to related resources around the web. The history of the problem is covered that, interesting to me, highlights a TSP board game proposed in the mid 1800's requiring the player to solve a 20-city instance. The history seems to highlight that Cook has been involved in the leading charge for finding solutions to the hardest instances for about 15 years.

An interesting area of the site are the pages that describe the methods for solving the TSP. These pages suggest that finding good solutions, even optimal solution to large TSP problems is hard, although the methods for verifying the optimality of a solution are harder (at least more time consuming). The approachers described include: control zones, sub-tour elimination, cutting planes, local cuts, branching, and accuracy, the last few of which have yet to be written. This section also provides in depth information and demonstration Java applets are provided on the historic cutting plane method proposed in the 1954 paper Solution of a Large-Scale Traveling-Salesman Problem.

Naturally, there is a section dedicated to the CONCORDE solver, providing a downloadable version of the solver with source code for academic and general research use. Versions of this solver have been used by Cook and colleagues to find some of the largest TSP solutions known to computer science. In fact, there is a page dedicated to world records for TSP instances, which is held by Cook and collaborators for the solution of a 85,900 node VLSI instance in 2006.

The remainder of the site provides information on applications for TSP research (such as the CONCORDE solver), a gallery of TSP problems and solutions, and a nice Google Maps TSP mashup for solving for solving ad hoc instances defined by users. Interestingly, the site provides two in-browser flash games for solving the TSP. The first is a single-player game that involves a player finding a minimal tour called Tour Finder, and the second is a two-player game that faces the players off against each other called Tour Race. Finally, the site provides a set of test TSP instances in addition to TSPLIB including a nearly 2 million node world map, 25 instances of cities around the world, and 102 VLSI instances.

Reading over the material from Cook's site consolidated a lot of ideas I had for the next iteration of the human based TSP solver application. I am thinking about ranking problems by their general difficulty (number of cities, discretised on a log scale), and offering users to contribute toward one of a set of different instance difficulty levels (easy, medium, hard, insane). I was also thinking of assigning users "experience levels" based on the number and type of contributions.

Regarding the contribution mechanism, I was thinking of allowing the user to select the difficultly of the sub-problem (number of cities), allow help in the sub-problems (nearest neighbour solutions, common solutions, broader context), and allowing sub-problems to be resized. Regarding the aggregate solutions, I was thinking of showing the nearest neighbour solution, the probabilistic-best crowdsourced solution as well as the optimal solution (if known).

At the very least, reading Cook's page has motivated me to ensuring the application can support a wide array of large (up to 100K) and small (<100) instances of the TSP, and to perhaps focus on the less regular instances available (such as geographic-based rather than VLSI instances).