Record traveling salesman solution --
New heuristic approach to classic linear programming problem yields big dividend
From: TechWeb, June 29, 1998
By R. Colin Johnson
Houston - Rice University researchers have proved an optimal route for a
traveling salesman visiting the largest 13,509 U.S. cities, topping a previous
record of routing the 7,397 largest U.S. cities set in 1994. "Finding an optimal
solution is only half the work, the other half is proving that it is optimal," said
professor Robert Bixby, who shared the victory with fellow Rice professors
David Applegate and William Cook, along with Vasek Chvatal of Rutgers
University.
"You actually get a read-me file with our solution that tells you how to prove it's
optimal for yourself on your own computer-you don't have to repeat the whole
calculation to prove our solution is optimal," said Bixby. The traveling-salesman
problem (TSP) has become a classic benchmark problem for computers.
Although easy to formulate-one is required to find the optimal route a salesman
should take when visiting a number of cities-the solution becomes very difficult
to find as the size of the problem increases. The specific problem is also a good
test case for a more general class of problems called "mixed-integer
programming (MIP) problems that occur in a wide variety of scientific and
technical computing areas."
The actual solution of the 13,509 cities required a cluster of three Digital
AlphaServer 4100s with a total of 12 processors, plus a cluster of 32 Pentium II
PCs, located in Rice University's Duncan Hall. But the calculation still took
approximately three months to finish. The program was enormous-a printout of
the code runs over 1,000 pages, according to Chvatal.
"At least you don't need 'big iron' anymore to do LP [linear programming]," said
Bixby, referring to the fact that only a network of microprocessors, as opposed
to a supercomputer, was used when cracking "USA13509"-jargon for the TSP
applied to the top U.S. 13,509 cities.
Linear programming algorithms could not have cracked USA13509 if not for
smart heuristics, used to eliminate large segments of the geometrically
expanding solution "space," which grew to more than 13,000 dimensions.
Other smart technologies seek to automate the search through the solution
space for the optimal point with self-organizing algorithms that adapt until they
reach a good solution. Unfortunately, according to Bixby, such genetic
algorithms and the like can't provide an answer to the second part of the
problem-proving that the solution is the best, or "optimal."
"You have absolutely no idea how good a genetic algorithm's solution is.
Besides, if all you want is good algorithms without proof, there are better ways
than genetic algorithms," he said. The latest success was achieved through a
divide-and-conquer strategy using smart heuristics. Because the TSP is "NP
Complete," which means that the number of steps to reach a solution rises
extremely fast with the number of variables, the team encapsulated its own
mathematical expertise into a set of decision-making rules.
"The problem is a classical hard problem," said Bixby. "Pathological examples abound-there are 100 city problems that cannot be solved today or ever." So most researchers work from real databases of real cities that don't contain pathological examples, such as "TSPlib95" at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
There, the smallest real route that has not been solved is 2,103 cities. Why less
than USA13509? Because some examples are harder to solve than others. For
instance, a million-city route could be plotted easily if all the cities were lined up
in a row. Naturally occurring groups tend to steadily increase in complexity, as
is the case with the U.S. cities the Rice researchers attacked.
First, the Rice researchers wrote an incomplete, abbreviated mathematical
description of the problem in order to create a partial description and solve it.
Then they looked at the solution space geometrically and imaged "cutting
planes" that severed away regions of the space where illegal solutions existed.
"For instance, the computer might allow a solution where we send one-third of a
salesman one way and two-thirds of a salesman another way, but of course that
is not a legal solution," said Bixby. Next, the heuristics encapsulate a
branch-and-bound procedure that picks likely variables to bound and then
explores each resulting branch before choosing the direction in which to commit.
The team also developed a new "branching rule" called "strong branching,"
which was particularly useful in the solution of the difficult integer aspects of
the problem. This branching rule has subsequently become widely available in
several commercial MIP solvers.
Local cuts
For the latest additions to the gigantic program, the Rice researchers have used
a technique called local cuts, which create small, local cutting planes without
having to look at the geometry of the problem. "I can give it a list of 15 or 20
cities that have been troublesome and it guarantees to find what is wrong and
get an exact solution without having to exhaustively search every possible
route," said Bixby.
Bixby enumerated the components of what he called an interdisciplinary solution
to USA13509: polyhedral combinatorial optimization, integer and linear
programming, parallel computing and graph theory. Bixby cited possible
applications of their TSP, such as drilling holes in printed-circuit boards,
switching fiber-optic communications networks or routing telephone calls.
The TSP project is supported by Rice University, the Center for Research on
Parallel Computation (CRPC); Digital Equipment Corp.; and the Keck
Foundation, as part of Rice's W.M. Keck Center for Computational Discrete
Optimization.
Copyright ® 1998 CMP Media Inc.
|