Cracking nug30 on the Grid  1 2 3 4
Using Alliance resources and Alliance-deployed software tools, a team from Argonne National Laboratory and the University of Iowa created what one researcher called one of "the largest Grid computing successes for the Alliance" to date. Along the way, they solved a mathematical riddle that had stood for more than 30 years.


A classic problem in the realm of mathematics known as discrete optimization is nug30, a quadratic assignment problem (QAP) posed by three mathematicians in 1968 (one of them a fellow named Nugent, thus "nug"). In the nug30 problem, 30 facilities must be placed at 30 locations so as to minimize the total cost of transferring materials among the facilities. The problem was put forth as a test problem—a puzzler for fellow math whizzes to chew on. But problems like it arise in the real world, too, in everything from designing the layout of a hospital or factory to designing circuits.


quadratic assignment problem

Illustration of a quadratic assignment problem with only four locations and four facilities. Cracking the nug30 problem required proving the optimal layout for 30 facilities at 30 locations.




Despite its seeming simplicity, nug30 is monsterously difficult to solve. Actually, until a grid of computational resources from eight sites around the world was recently focused on the problem, it hadn't been solved at all. In June researchers from Alliance partners University of Iowa and Argonne National Laboratory cracked nug30, proving the optimal layout for those 30 facilities for the first time in the problem's three-decade history.


"Thirty-two years is a very, very long time in computational mathematics," says Kurt Anstreicher, a professor of management sciences at the University of Iowa. "Most computational problems that were difficult 30 years ago are now trivial because of enormous advances in algorithms and computational power." Anstreicher and his student Nathan Brixius designed the algorithm that solved the nug30 problem. They worked in collaboration with Jeff Linderoth of Argonne and Jean-Pierre Goux of Argonne and Northwestern University to implement their QAP algorithm on the Grid.


Access Online | Posted 10-24-2000






 up 1 2 3 4