Computer grid cracks problem - nug30 quadratic assignment problem - Brief Article

Science News, August 19, 2000 by I.P.

Some problems are so difficult that it takes a large network of enormously powerful computers to come up with a solution. Such a network, or computational grid, now has solved a challenging optimization problem first posed in 1968. The problem--called the nug30 quadratic assignment problem--asks how to assign 30 facilities to 30 fixed locations so as to minimize the total cost of transferring material between facilities.

Although the problem looks simple, the number of possible assignments is extremely large, says Kurt M. Anstreicher of the University of Iowa in Iowa City. "If you could check a trillion per second, this process would take over 100 times the age of the universe," he says. Anstreicher and his Iowa collaborator Nathan W. Brixius worked with researchers at the Argonne (Ill.) National Laboratory to develop the algorithms and software necessary to tackle the previously unsolved problem.

At its peak earlier this year, this computational endeavor involved more than 1,000 computers working simultaneously at eight institutions in different parts of the world. Cracking the problem required nearly a week. "This was, to our knowledge, one of the largest computations ever performed to solve a discrete optimization problem," Anstreicher says.