Researchers Forge New Optimal Path For Traveling Salesman Problem

June 08, 1998

HOUSTON, Texas, June 8, 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 record of 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 for the most economical way a salesman can tour five cities, a computer can be used to calculate the lengths of all 120 possible different 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 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, Noah Harding Professor of Computational and Applied Mathematics (CAAM) at Rice. "Over the past 4 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 CAAM. "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.

"One of the basic computational tools used in the standard approaches to the TSP, including ours, is linear programming [LP]," Bixby says. "ndeed, the TSP is one of the more demanding uses of this tool, and over the last 10 years has led to numerous advances in the commercial LP software that we were using. These advances then became available to commercial and research users throughout the world. Specially for MIP, we developed a new 'branching rule' called 'strong branching,' which is particularly useful in the solution of difficult integer programs. This branching rule is now available in several commercial MIP solvers."

Of the team's ongoing TSP research, Rutgers Professor of Computer Science Chvatal says, "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."

The TSP project is supported by Rice University and Rice's Computer and Information Technology Institute; 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 more information, contact Kathy El-Messidi, External Relations, CRPC, Rice University, (713) 285-5181, or by email: elmessy@rice.edu

Editors: 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.
-end-


Rice University

Related Rice Articles from Brightsurf:

C4 rice's first wobbly steps towards reality
An international long-term research collaboration aimed at creating high yielding and water use efficient rice varieties, has successfully installed part of the photosynthetic machinery from maize into rice.

Rice has many fathers but only two mothers
University of Queensland scientists studied more than 3000 rice genotypes and found diversity was inherited through two maternal genomes identified in all rice varieties.

Rice rolls out next-gen nanocars
Rice University researchers continue to advance the science of single-molecule machines with a new lineup of nanocars, in anticipation of the next international Nanocar Race in 2022.

3D camera earns its stripes at Rice
The Hyperspectral Stripe Projector captures spectroscopic and 3D imaging data for applications like machine vision, crop monitoring, self-driving cars and corrosion detection.

Climate change could increase rice yields
Research reveals how rice ratooning practices can help Japanese farmers increase rice yields.

Breeding new rice varieties will help farmers in Asia
New research shows enormous potential for developing improved short-duration rice varieties.

High-protein rice brings value, nutrition
A new advanced line of rice, with higher yield, is ready for final field testing prior to release.

Rice plants engineered to be better at photosynthesis make more rice
A new bioengineering approach for boosting photosynthesis in rice plants could increase grain yield by up to 27 percent, according to a study publishing January 10, 2019 in the journal Molecular Plant.

Can rice filter water from ag fields?
While it's an important part of our diets, new research shows that rice plants can be used in a different way, too: to clean runoff from farms before it gets into rivers, lakes, and streams.

Rice plants evolve to adapt to flooding
Although water is essential for plant growth, excessive amounts can waterlog and kill a plant.

Read More: Rice News and Rice Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.