Search
Sites and Affiliations
Leadership
Research and Applications
Major Accomplishments
Frequently Asked Questions
Knowledge and Technology Transfer
Calendar
Education and Outreach
Media Resources
Technical Reports and Publications
Parallel Computing Research - Our Quarterly Newsletter
Contact Information
CRPC Home Page

UniGuide Featured Site

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.