Volume 6, Issue 3
Fall 1998

Volume 6, Issue 2
Spring/Summer 1998

Volume 6, Issue 1
Winter 1998

Volume 5, Issue 4
Fall 1997

Volume 5, Issue 3
Summer 1997

Volume 5, Issue 2
Spring 1997

Volume 5, Issue 1
Winter 1997

Volume 4, Issue 4
Fall 1996

Volume 4, Issue 3
Summer 1996

Volume 4, Issue 2
Spring 1996

Volume 4, Issue 1
Winter 1996

Volume 3, Issue 4
Fall 1995

Volume 3, Issue 3
Summer 1995

Volume 3, Issue 2
Spring 1995

Volume 3, Issue 1
January 1995

Volume 2, Issue 4
October 1994

Volume 2, Issue 3
July 1994

Volume 2, Issue 2
April 1994

Volume 2, Issue 1
January 1994

Volume 1, Issue 4
October 1993

Volume 1, Issue 3
July 1993

Volume 1, Issue 2
April 1993

Volume 1, Issue 1
January 1993

Recently, CRPC researcher Bob Bixby (Rice University) and colleagues David Applegate (AT&T Bell Labs), V‰sek Chvatal (Rutgers University), and William Cook (Bellcore) using a network of a SPARC 2, DEC Station 5000, SGI workstation, and others (a total of 50 workstations) determined an optimal route for traveling through 3038 cities, a dramatic step beyond the old record of 2392 cities, set by Padberg and Rinaldi. The problem is commonly referred to as the "Traveling Salesman Problem."

Finding an optimal route becomes more challenging as the number of cities involved increases. For instance, to solve for the most economical way for a traveling salesman to tour five cities the researcher can take a straightforward method, having the computer calculate the lengths of all 120 different routes to find the shortest one. This calculation could be performed in a fraction of a second. However, using the same method to figure the optimal route for a hundred cities could take billions of years. How can a more efficient solution be reached?

The researchers designed an algorithm based on a technique called "branch and cut," which steadily improves the collection of linear inequalities describing the set of feasible solutions. Many other groups have created algorithms that can reach approximate (within 2%) solutions for this problem, calculating approximate optimal routes for 1000 cities in a few minutes. Improved versions of those techniques were used here to get upper bounds. The difficult part was to drive up the lower bound and prove optimality. Calculations for the 3038 cities problem required one and one-half years of computer time.

The Traveling Salesman Problem is typical of a large class of "hard" optimization problems that have intrigued mathematicians and computer scientists for years. Most important, it has applications in science and engineering. For example, in the manufacture of a circuit board, it is important to determine the best order in which a laser will drill thousands of holes. An efficient solution to this problem reduces production costs for the manufacturer.