Researchers Focus Efforts of 1,000 Computers to Crack Optimization Challenge Problem

It took 1,000 computers in 13 locations around the world a week to solve, but a 32-year-old mathematics problem has surrendered to an algorithm (a set of problem-solving instructions) developed by researchers at Argonne, the University of Iowa and Northwestern University.

If the problem, known as NUG30, could have been run on a single, fast computer workstation, it would have taken approximately seven years to complete, according to Argonne senior computer scientist Steve Wright. By using a large number of computers in parallel, NUG30 required a little less than a week of continuous computing. Almost 1 million linear assignment problems were solved each second during the week-long run.

NUG30 was believed only a year ago to be out of reach for the current generation of optimization algorithms and computing platforms. It was solved by the teamwork of two research groups—the optimization and grid computing communities. Argonne plays a lead role in both areas.

The method used to crack the problem holds promise in such real-world applications as the layout of departments in a hospital or manufacturing facility and the design of aircraft cockpit panels and computer chips. The problem involves assigning 30 facilities to 30 fixed locations so as to minimize the total cost of transferring material between the facilities. NUG30 was first proposed as a test of computer capabilities but remained unsolved because of its complexity.

“The number of assignments is so large that even if you could check a trillion per second, this process would take over 100 times the age of the universe,” noted Kurt Anstreicher, a researcher at the University of Iowa. Anstreicher and his student Nate Brixius worked with Argonne researchers Jean-Pierre Goux and Jeff Linderoth to solve NUG30.

The algorithm reduced the number of assignments to a manageable level by eliminating possibilities that could not lead to an optimal assignment. To explore the remaining possibilities quickly and cheaply, the team enlisted the untapped power of hundreds of underused workstations connected via the Internet.

The researchers used the Master-Worker runtime support library, which enables diverse computers to be used as a single parallel computing platform. The library was devel-oped as part of metaNEOS, a project that ties together researchers in optimization and distributed computing at the University of Wisconsin, Northwestern University and other institutions. Argonne’s Steve Wright is metaNEOS’ lead investigator.

The runtime support library runs on the Condor system developed at the University of Wisconsin. It uses such resources as PCs and the idle time on user workstations, so the cost of performing computations is low. At its peak, the program enlisted more than 1,000 computers simultaneously at universities and supercomputing centers across the country and in Italy.

“This was one of the largest and most complex computa-tions ever performed to solve a discrete optimization problem,” said Wright. “It signals a new era in the use of com-putational grids for solving complex problems in numerical computing.”

For more information please contact Dave Jacque at 630-252-5582

Next: Research Facilities