You've got 30 treatment areas in a hospital, with doctors and nurses shuttling among them. What's the most efficient way to lay them out? This applied math problem, known as Nug30, is harder than it sounds. "If you checked a trillion possibilities a second, it would take you 100 times the age of the universe to confirm the optimal solution," says Kurt Anstreicher, a mathematician and management expert at the University of Iowa. Yet he and colleagues at Argonne National Lab have managed to crack it.
The group enlisted collaborators at universities around the world to volunteer their computers. Using Condor, software that allows many computers to work as one, the Nug30 team hooked the machines together into a grid through the Internet. A main controller farmed out the computations to machines that were free and coordinated the results they sent back. First, the researchers devised a shared computer program that quickly eliminated solutions that could not possibly be optimal. This cut the set of possibilities to a pool of only 12 billion potential solutions— still a hairy computational task. Then the grid of computers, roughly 2,500 in all, crunched out the optimal answer in a week. "It was the equivalent of about seven years of computation on a fast workstation," says Anstreicher.
The Nug30 team wanted to publicize the power of the grid approach. "Hopefully, somebody will call up with another problem, like laying out components on a computer chip or designing an efficient airplane cockpit," Anstreicher says.
