Shorter, More Efficient Circuits, Networks
From: Microelectronics Technology Alert, July 24, 1998
Even the most hard-nosed travel department doesn't care all that much about how efficiently (in terms of distance traveled, not expense accounts) a salesperson makes the rounds of prospects to be visited. But the classic traveling salesman mathematical problem is of vital importance to people plotting circuits on chips and networks of computers. Taking the shortest possible route among all of the points can mean getting more functions onto the same piece of chip real estate or the fastest linking of computers (or telephones, electricity users) at the least cost.
Rice University mathematicians have determined a breakthrough solution to the traveling salesman problem (TSP). In classic TSP terms, they have solved the problem for 13,509 cities with populations of more than 500 people. This comes near to doubling their previous record, set in 1994, of 7397 cities.
TSP belongs to a class of hard optimization problems with science and engineering applications that mathematicians and computer scientists has grappled with for years. The difficulty goes up exponentially as the number of cities or other points to be hit rises. To find the shortest path for a salesman to tour five cities a computer can calculate the lengths of all 120 possible different routes and find the shortest one in a fraction of a second. But the same method to find the optimal route for 100 cities could take billions of years.
Mathematical models and high-performance computing have been used by the Rice researchers since 1988 to develop a more efficient algorithm. In 1992 they solved for 3038 cities using 50 workstations and a cutting planes algorithm. In this algorithm, a collection of linear inequalities describing the set of feasible solutions is steadily improved. By 1994, the team had solved for 4461 cities and got up to 7397 in 1994.
Now they have solved for 13,509 with a cluster of three Digital AlphaServer 4100s, a total of 12 processors, and a cluster of 32 Pentium-II PCs. The calculation was not instantaneous: It took three months. The mathematicians have come up with an entirely new system for solving TSP, focusing on methods than can scale up to instances having 10,000 or more cities.
Early last year the team devised a technique for greatly extending the use of linear programming methods for TSP. Ideas from polyhedral combinatorics were combined with combinatorial optimization, integer and linear programming, computer science data structures, and algorithms, parallel computing, software engineering, numerical analysis, and graph theory.
TSP can be applied directly to problems such as drilling holes in printed circuit boards, designing fiber optic communications networks, routing helicopters around oilrigs and picking up coins from phone booths. But the big application is mixed integer programming (MIP) problems. One of the basic computational tools used in standard TSP approaches is linear programming (LP) and TSP is one of the more demanding uses of the LP tool. Numerous advances in commercial LP software have come from TSP work. Specifi cally, the Rice mathematicians have developed a new branching rule, strong branching, for MIP.
Details: William J. Cook, Professor, Computational and Applied
Mathematics, 3020 Duncan Hall, Rice University, Houston, TX 77251. Phone:
713-737-5667. Internet: email@example.com. (July, Fax: +49-228-738771.
Copyright 1998, John Wiley & Sons, Inc., New York, NY 10158
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