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

--
Dr David K Smith, School of Mathematical Sciences, University of Exeter,
Exeter, Devon, UK
email:[log in to unmask]
WWW:  http://www.maths.ex.ac.uk/~DKSmith/HomePage.html
 ... to those who never walk up mountains, visiting the bank, the post
  office and the dry cleaners on the same day is considered a triathlon.
                                                          (Muriel Gray)




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%