A problem in combinatorial optimization first proposed in 1968 as a test of computer capabilities has been solved, according to an announcement today by researchers from Northwestern University, the University of Iowa and Argonne National Laboratory.
Only a year ago the problem, a quadratic assignment problem (QAP), known as NUG30, was thought to be out of reach for the current generation of optimization algorithms and computing platforms. Thirty-two years after the problem was proposed, it was solved over a seven-day period on a collection of more than 1000 computers around the world.
"If the problem could have been run on a single, fast computer workstation, it would have taken approximately seven years to complete," said Jean-Pierre Goux, a research associate at the Optimization Technology Center at Northwestern University and Argonne National Laboratory. "By using a large number of computers in parallel, NUG30 required a little less than a week of continuous computing."
The project is one of the largest and most complex computations ever performed to solve a discrete optimization problem, signaling a new era in the use of computational grids for solving complex problems in numerical computing.
Thirty facilities were assigned to 30 fixed locations to minimize the total cost of transferring material between the facilities. QAP problems such as this arise in many applications including decisions about the layout of departments in a hospital or manufacturing facility and design of VLSI chips.
"The complexity of a QAP with 30 locations is really hard to imagine," said 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 more than 100 times the age of the universe."
Goux and Anstreicher collaborated with colleagues Nate Brixius (University of Iowa) and Jeff Linderoth (Argonne National Laboratory) 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. It was 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 Northwestern, the University of Wisconsin, Argonne 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," said Argonne's 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," said Northwestern's Goux.
At its peak, the program enlisted more than 1,000 computers simultaneously at Northwestern University, 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 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.
"NUG30 only hints at the incredible future for the use of computational grids for solving complex problems in numerical computing," said Steve Wright, of Argonne's Mathematics and Computer Science Division.
Further information on the NUG30 solution can be found at http://www.mcs.anl.gov/metaneos/nug30; contact Jean-Pierre Goux, Optimization Technology Center at Northwestern University and Argonne National Laboratory, at goux@ece.northwestern.edu