nug30 solved on Grid
In what one researcher called one of “the largest Grid computing successes for the Alliance” to date, researchers at National Computational Science Alliance partners University of Iowa and Argonne National Laboratory announced that they used the Partnerships for Advanced Computational Infrastructure (PACI) Grid to solve the nug30 quadratic assignment problem (QAP). Nug30 had gone unsolved since 1968 when it was first proposed as a test problem in the area of applied mathematics known as location theory.
Kurt Anstreicher, a professor of management sciences at the University of Iowa, and his student Nathan Brixius designed the algorithm that solved the nug30 problem. They worked in collaboration with Jeff Linderoth and Jean-Pierre Goux of Argonne to parallelize their QAP algorithm using a variety of Alliance Grid resources and software tools.
Processors from Argonne, the University of Wisconsin, Georgia Tech’s Interactive High Performance Computing Laboratory, the Italian Istituto Nazionale di Fisica Nucleare, NCSA, the Albuquerque High Performance Computing Center, Columbia University, and Northwestern University using five different computing platforms were harnessed in the seven-day nug30 run—effectively creating a single, integrated parallel computing platform. The QAP solution consumed more than 96,000 CPU-hours. An average of about 650 processors were used to solve the problem at any given time, with a peak of 1,009.
“The most important thing to remember here is that this wasn’t a demo,” says Miron Livny, a computer science professor at Wisconsin who heads the Condor project. “The nug30 team wasn’t working in any sort of bubble. They were using generic grid middle-ware, on production grid resources, in a very dynamic multi-user environment.”
In QAPs like nug30, there are a set of n locations and a set of n facilities, and each facility must be assigned a location. To measure the cost of each possible assignment, the flow between each pair of facilities is multiplied by the distance between the pair’s assigned locations, and then a sum is taken over all of the pairs. In nug30, for example, 30 facilities must be assigned to 30 fixed locations, and the goal is to find the assignment that minimizes total cost of transferring material between the facilities.
“The complexity of a QAP like nug30 is really hard to imagine,” says Anstreicher. “Without the use of metacomputing, the solution process would have required about 7 years on a fast workstation, even with our very sophisticated algorithm.”