CONTACT: GARY GALLUZZO
100 Old Public Library
Iowa City IA 52242
(319) 384-0009; fax (319) 384-0024
Release: June 29, 2000
UI researchers solve 32-year-old mathematics problem
IOWA CITY, Iowa -- 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
"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 seven years
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."
For more information about the nug30 problem and its solution see the web
pages at http://www.mcs.anl.gov/metaneos/nug30/.