12 June 1998

Staggering Progress In Travelling Salesman Problem

The Travelling Salesman Problem (TSP) has intrigued - and exasperated - mathematicians and computer scientists for years. A typical example of the mind-bending class of optimization problems, the puzzle involves finding an optimal route for a fictitious door-to-door insurance salesman when travelling through a given number of cities. Sound easy? A computer can determine the most economical way to tour five cities by calculating the lengths of all 120 possible different routes in just a fraction of a second. However, raise that number to a hundred cities and the computer will be doing its sums for the next billion or so years.

Since 1988, a research team from Rice University has been refining mathematical models and using high-performance computing to outwit the problem. In their latest breakthrough they have come up with a solution for a staggering 13,509 cities with populations of more than 500 people.

"The solution of 'usa13509' is certainly a high point of our research project," says William Cook, Noah Harding professor of computational and applied mathematics. "Over the past four years, we have written an entirely new system for solving the TSP, focusing on methods that can scale up to instances having 10,000 or more cities. The breakthrough in our work came last year when our team devised a technique for greatly extending the use of linear programming methods for the TSP."

The first step on the road to breakthrough was the invention of an algorithm based on a technique called "cutting planes" - a way of improving the collection of linear inequalities describing a set of feasible solutions. Using a cluster of three Digital AlphaServer 4100s and a batch of 32 Pentium-II PCs, the team were able to complete their feat. The calculation took about three months.

"One of the most exciting aspects of this work was the fact that it was truly interdisciplinary," says Rice professor and collaborator Robert Bixby. "It involves ideas from polyhedral combinations and combinatorial optimization, integer and linear programming, computer science data structures and algorithms, parallel computing, software engineering, numerical analysis, graph theory and more." Phew.

Vasak Chvatal of Rutgers University, who also played a role in the breakthrough, adds: "It's addictive. No matter how much progress you make, you always have the nagging feeling that you still did not nail down a couple of hunches that could bring about another quantum leap. And even if we stopped today, cold turkey, the sheer volume of what we have already done is overwhelming. If we printed our code, it would run to well over a thousand pages."

GoGo Further - Graphic of Solution