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

UniGuide Featured Site

You can get there from here
Research team finds record solution to classic math problem

From: Houston Chronicle, June 28, 1998
By Todd Ackerman, Staff

Every day during the school year in a rural county in upstate New York, 20 buses make roughly 800 stops to pick up students and take them to school.

Allan Weaver, a retired engineer who does volunteer work for the Southern Cayuga Central School District, says the intuition and experience that has determined the routes have worked pretty well over the years.

"But I'm the type who's always looking for objective solutions," he says. So Weaver contacted a Rice University math team that has come up with the world's best method of ascertaining the most economical travel routes.

The Rice team is still waiting on school district data to provide the answer, but one thing it already can tell school leaders might astound them: There are so many possible routes that the world's fastest computers could never enumerate them all.

The bus-routing problem is an example of the "traveling salesman problem," a classic math problem of such difficulty it is considered theoretically impossible to solve, although the Rice team has made breakthrough after breakthrough to reach the point that it could solve 99 percent of such problems.

Simply put, the traveling salesman problem asks for the shortest tour around a number of cities. It's fairly simple if there are only, say, four cities involved, in which case there would be 24 possible routes to check. But increase the tour to, say, 12 cities and suddenly there are 20 million possible pathways.

A computer can calculate the most economical way a salesman can make the four-city tour in a fraction of a second. But using the same method to figure the route for 100 cities could take billions of years.

But using algorithms, a kind of mathematical short-cut that saves computers from considering every possibility, Rice University researchers Robert Bixby, David Applegate and William Cook and Rutgers researcher Vaskek Chva-tal recently found the optimal route for touring a world-record 13,509 cities (every U.S. city with 500 or more people). Just to print in tiny type the number of possible routes to tour those cities would take up hundreds of pages.

"Because the routes explode so exponentially as you add cities, one great challenge about the traveling salesman problem is making the numbers comprehensible," says Bixby. "In the school district problem, for instance, the Earth will perish before computers could enumerate each possible bus route."

The traveling salesman problem actually predates 20th-century mathematics - long before it gained its contemporary name, the same premise was found in famous 18th- and 19th-century puzzles - but it wasn't until the advent of computers in the mid-1950s that it was solved for 49 cities (Washington, D.C., and a city in each of the then 48 states).

The problem had been solved for 2,392 cities in 1988 when Bixby, Applegate, Cook and Chvatal began working on it. In the following decade, they became the world's best at it - solving it for 3 ,038 cities, then 4,461, then 7,397 and now 13,509. In 1992, the 3 ,038-city achievement was chosen by Discover magazine as one of its top 50 stories.

Now, for the first time, math observers are talking about the problem crumbling, about an algorithm being developed that is so good it will produce excellent solutions to problems of the most calculated difficulty, even it can't absolutely guarantee it's the best possible solution.

Algorithms are mathematical recipes whose computer-implementation codes tell computers how to find the most economical routes without actually enumerating them all. Those short-cuts are based on patterns detected by both the mathematicians working on the problem and the computers themselves.

In the real world, solutions to the traveling salesman problem simplify scheduling and routing in the transportation industry - buses, airlines, delivery trucks and postal carriers. It also helps study biomolecular pathways, route computer networks' parallel processing and advance code writing and deciphering.

"The real appeal of the traveling salesman problem isn't solving the problems," says Bixby. "It's what you discover about the structure of a problem that makes it easier to solve other problems."

The Rice team is always looking for good examples to test their work. After reading a Wall Street Journal article about the "Extra Miler Club," an eccentric group of travelers whose members seek to eat Big Macs in every McDonald's in North America or visit every U.S. county, Cook offered to plan their trips based on the Rice team's method.

But after 10 years of cyberspace traveling, the Rice team may be ready for a rest from setting records for solving the traveling salesman problem. Members are now writing a book on the problem - complete with algorithms and codes that should enable other mathematicians to set records without having to reinvent what the Rice team learned.

Still, after investing a decade of their life on it, none of the researchers is ready to leave the traveling salesman problem. All have future plans related to it.

"It's addictive," says Chvatal. "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."

Sites & Affiliations | Leadership | Research & Applications | Major Accomplishments | FAQ | Search | Knowledge & Technology Transfer | Calendar of Events | Education & Outreach | Media Resources | Technical Reports & Publications | Parallel Computing Research Quarterly Newsletter | News Archives | Contact Information

Hipersoft | CRPC