IOWA CITY, Iowa, June 29, 2000 -- University of Iowa researchers and their colleagues at Argonne National Laboratory have solved an applied mathematics problem that had challenged computer scientists for 32 years.
Kurt Anstreicher, professor of management sciences in the Henry B. Tippie College of Business, and Nathan Brixius of Cedar Rapids, a doctoral student in the College of Liberal Arts computer science department, solved a quadratic assignment problem (QAP) in the field of location theory. Their collaborators were Jean-Pierre Goux and Jeff Linderoth of Argonne National Lab.
The challenge is to assign a given number of facilities to the same given number of locations, in this case 30, while minimizing the cost of flows between the facilities. A typical example of a "real world" application of such a problem involves deciding on the layout of departments within a hospital so as to minimize the total distance that patients must travel between departments. The problem, known as "nug30," was first proposed in 1968 as a test of computer capabilities, but remained unsolved because of its great complexity, ranking as one of the most difficult combinatorial optimization problems.
"The complexity of a QAP with 30 locations is really hard to imagine," notes Anstreicher. "You might think that with a fast computer you could just check all the possibilities, and see which one is best. But it turns out that even checking a trillion per second, the time it would take to check all the possible assignments is over 100 times the age of the universe."
The key to solving the problem was the design of a state-of-the-art algorithm, by Anstreicher and Brixius, and a high-performance "Master-Worker" distributed-processing computer system developed by Goux, Linderoth, and colleagues in the MetaNEOS project, a collaboration between Argonne, the University of Wisconsin, Northwestern University, and other institutions. The computation was performed on a grid of computers using the Condor high-throughput computing system, developed by Miron Livny and co-workers at the University of Wisconsin. At its peak, the problem enlisted the use of 1,009 computers working simultaneously at the University of Wisconsin, Argonne National Laboratory, Georgia Institute of Technology, National Center for Supercomputing Applications, Italian Istituto Nazional di Fisica Nucleare, Albuquerque High Performance Computing Center, Northwestern University and Columbia University.
Despite the vast number of computers involved, the solution required almost one week of continuous computing. If the problem could have been run on a single computer workstation, it would have taken approximately 7 years to complete.
Brixius plans to make use of the knowledge he has gained from the project in the near future, as he will begin working this fall on project management and scheduling software at Microsoft Corporation in Seattle. "This has been a great collaboration," says Brixius. "Working as part of a team has really showed me how a lot of pieces can come together to solve an extremely difficult problem."
University of Iowa General News 100 Old Public Library
For more information about the nug30 problem and its solution see the web pages at http://www.mcs.anl.gov/metaneos/nug30/.