We have completed maintenance on DiscoverMagazine.com and action may be required on your account. Learn More

The Nug Cracker

By Fenella Saunders
Nov 1, 2000 6:00 AMNov 12, 2019 6:39 AM


Sign up for our email newsletter for the latest science news

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.

1 free article left
Want More? Get unlimited access for as low as $1.99/month

Already a subscriber?

Register or Log In

1 free articleSubscribe
Discover Magazine Logo
Want more?

Keep reading for as low as $1.99!


Already a subscriber?

Register or Log In

More From Discover
Recommendations From Our Store
Shop Now
Stay Curious
Our List

Sign up for our weekly science updates.

To The Magazine

Save up to 40% off the cover price when you subscribe to Discover magazine.

Copyright © 2024 Kalmbach Media Co.