New Solution Determined for Traveling Salesman Problem

New Solution Determined for Traveling Salesman Problem

BY Gretchen Jacobson
Special to the Rice News
June 25, 1998

Rice University researchers David Applegate, Robert Bixby and William Cook
and Vasek Chvatal of Rutgers University have determined a breakthrough solution
to the Traveling Salesman Problem (TSP), a method for finding an optimal path
for a salesman to take when traveling through a specified number of cities.

The researchers have solved the TSP for 13,509 U.S. cities with populations
of more than 500 people, a dramatic step beyond their previous solution for
7,397 cities, set in 1994.

The TSP is typical of a class of hard optimization problems with applications
in science and engineering that has intrigued mathematicians and computer scientists
for years. Finding an optimal route for the TSP becomes more challenging as
the number of cities increases. For example, to solve the most economical way
a salesman can tour five cities, a computer can be used to calculate the lengths
of all possible routes and find the shortest one in a fraction of a second.
However, using the same method to figure the optimal route for 100 cities could
take billions of years. The research team has been developing mathematical models
and using high-performance computing since 1988 to develop a more efficient
solution.

The researchers’ first breakthrough was a record 3,038 cities set in 1992,
using 50 workstations and an algorithm they designed based on a technique called
"cutting planes." The technique steadily improves the collection of
linear inequalities describing the set of feasible solutions. This achievement
was recognized by Discover magazine as one of its top 50 science stories that
year. By 1993, the team had solved the TSP for 4,461 cities. This year, the
TSP researchers surpassed their 1994 record by using a cluster of three Digital
AlphaServer 4100s (a total of 12 processors) and a cluster of 32 Pentium-II
PCs located in Rice University’s Duncan Hall. The calculation took approximately
three months from start to finish.

"The solution of ‘usa13509’ is certainly the high point of our research
project," says Cook, the Noah Harding Professor of Computational and Applied
Mathematics (CAAM) at Rice. "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
early last year when our team devised a technique for greatly extending the
use of linear programming methods for the TSP."

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

Direct applications of the TSP range from drilling holes in printed circuit
boards to designing fiber-optic communications networks, and from routing helicopters
around oil rigs to picking up coins from telephone booths. The real mission
of this work, however, is the study of techniques that can be used to solve
a more general class of applied problems known as mixed-integer programming
(MIP) problems. Bixby has created the world’s leading software for MIP.

"Specially for MIP, we developed a new ‘branching rule’ called ‘strong
branching,’ which is particularly useful in the solution of difficult integer
programs," Bixby says. "This branching rule is now available in several
commercial MIP solvers."

The TSP project is supported by Rice University and Rice’s Computer and Information
Technology Institute (CITI); the Center for Research on Parallel Computation
(CRPC); Digital Equipment Corporation; and the Keck Foundation, as part of Rice’s
W.M. Keck Center for Computational Discrete Optimization.

For a map of the United States showing the TSP solution for 13,509 cities see:
http://www.crpc.rice.edu/CRPC/Images/TSP/tsp.gif.