NUG30 press release
Argonne, Illinois, 6/27/2000.
Researchers from the University of Iowa and Argonne National
Laboratory today announced the solution of a challenge problem in
combinatorial optimization that has stood for 32 years. The problem, a
quadratic assignment problem (QAP) known as NUG30, was solved over a
seven-day period on a collection of more than 1000 computers around
the world. It was believed only a year ago to be out of reach for the
current generation of optimization algorithms and computing platforms.
The problem involves assigning 30 facilities to 30 fixed locations so
as to minimize the total cost of transferring material between the
facilities. QAP problems such as this arise in many applications,
including deciding the layout of departments in a hospital or
manufacturing facility, and the design of VLSI chips. 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,"
noted Kurt Anstreicher, a researcher at the University of Iowa. "You
might think that with a fast computer you could just check all the
possible assignments of facilities to locations, and choose the best
one. But the number of assignments is so large that even if you could
check a trillion per second, this process would take over 100 times
the age of the universe."
Anstreicher collaborated with colleagues Nate Brixius (Iowa), Jean-Pierre Goux (Argonne National Laboratory and Northwestern
University), and Jeff Linderoth (Argonne) to solve NUG30.
Keys to solving the problem were the design of a state-of-the-art
algorithm, by Anstreicher and Brixius, and its implementation on an
extremely powerful computing platform.
The algorithm reduced the number of assignments to a manageable level
by repeatedly eliminating possibilities that could not lead to an
optimal assignment. To explore the remaining possibilities quickly
and cheaply, the team made use of the untapped power of hundreds of
underutilized workstations connected via the Internet. Computers were
accessed via a high-throughput computing system known as Condor,
developed by Miron Livny and co-workers at the University of
Wisconsin. To implement the algorithm, they used the Master-Worker
distributed-processing interface to Condor developed by Goux,
Linderoth, and their colleagues Sanjeev Kulkarni and Mike Yoder as
part of MetaNEOS, a project that ties together researchers in
optimization and distributed computing at the University of Wisconsin,
Argonne, Northwestern University, and other institutions. The Globus
toolkit was used to obtain some of the computational resources used in
the NUG30 calculation.
``The Condor system and the Master-Worker interface are able to manage
a large, diverse grid of computational resources, allowing us to use
it as a single parallel computing platform,'' noted Jeff Linderoth.
Because Condor utilizes such resources as PCs and the idle time on
user workstations, the cost of performing computations is low. ``The
availability of this powerful, easily programmable, low-cost computing
platform has tremendous implications for the solution of complex
optimization problems and for computational science in general,''
Jean-Pierre Goux added.
At its peak, the program enlisted more than a thousand computers
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. Some of these machines were PCs
from dedicated clusters and others were components of supercomputers,
but many were workstations on the desks of individuals unconnected
with the project.
If the problem could have been run on a single, fast computer
workstation, it would have taken approximately 7 years to complete.
By using a large number of computers in parallel, NUG30 required a
little less than a week of continuous computing.
``This was one of the largest and most complex computations ever
performed to solve a discrete optimization problem,'' said Steve
Wright, of Argonne's Mathematics and Computer Science Division. ``It
signals a new era in the use of computational grids for solving
complex problems in numerical computing.''
Further information on the NUG30 solution can be found at
http://www.mcs.anl.gov/metaneos/nug30
metaneos@mcs.anl.gov
Last modified: Mon Jul 3 23:19:01 CDT 2000
