Computer grid cracks problem

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.

Use up and down arrow keys to explore.Use right arrow key to move into the list.Use left arrow key to move back to the parent list.Use tab key to enter the current list item.Use escape to exit the menu.Use the Shift key with the Tab key to tab back to the search input.