NCSA NEWS

Researchers at the University of Iowa and Argonne National Laboratory announced recently that they solved the nug28 quadratic assignment problem using the Condor high-throughput computing system developed at the University of Wisconsin, one of the National Computational Science Alliance's Partners for Advanced Computational Services (PACS) and a member of the Enabling Technologies team.

The quadratic assignment problem (QAP) is a standard model in the area of applied mathematics known as location theory. In such a problem, 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.

The goal is to find the assignment that minimizes total cost. Despite the simplicity of the problem statement, QAPs are incredibly difficult to solve to optimality.

"The QAP is, for its size, among the hardest of all combinatorial optimization problems," says Kurt Anstreicher, a professor of management sciences at the University of Iowa. Anstreicher and his student Nathan Brixius designed the algorithm that solved the nug28 problem. This problem is derived from a particularly notorious QAP now known as nug30, which was first suggested as a test problem in 1968. Despite enormous advances in computational power and discrete optimization theory, the nug30 problem remains unsolved.

"We designed a state-of-the-art algorithm," says Anstreicher, "but without a state-of-the-art computational platform we would never be able to attack a QAP like nug28." Anstreicher and Brixius worked in collaboration with Jeff Linderoth and Jean-Pierre Goux of Argonne National Laboratory, an Alliance partner, to implement their QAP algorithm using the Master-Worker runtime support library.

The Master-Worker library, developed by researchers at Argonne, Northwestern University, and Wisconsin as a part of the MetaNEOS project, uses Wisconsin's Condor system to send work to a potentially large number of processors working in parallel. The system is well suited to algorithms that can exploit a high degree of paralellism with relatively low bandwidth requirements.

Condor harnesses the power of desktop computers and commodity clusters by monitoring their status and running jobs on them when they are available. Machines at Wisconsin and the Albuquerque High Performance Computing Center, both Alliance PACS site, ran the computation, as well as computers at the Italian Instituto Nazionale di Fisica Nucleare.

The solution consumed over 18,000 CPU-hours in just over four days. About 200 workstations were being used to solve the problem at any given time. The computation would have taken over 400 days to complete on a single workstation.

"Optimization is one example of the many scientific disciplines that have been served by Condor," says Miron Livny, a computer science professor at Wisconsin who heads the Condor project. "By harnessing the huge computing power of desktop and commodity hardware and making it accessible to the scientific community, Condor enables computationally intensive science and the development of a new generation of computing technology."

The National Computational Science Alliance is a partnership to prototype an advanced computational infrastructure for the 21st century and includes more than 50 academic, government and industry research partners from across the United States. The Alliance is one of two partnerships funded by the National Science Foundation's Partnerships for Advanced Computational Infrastructure (PACI) program, and receives cost-sharing at partner institutions.

Access Online | Posted 5-9-2000