Eureka! U of Iowa researchers solve the mystery of NUG30

• A solution to the math puzzle had eluded

  experts for 32 years.

Professor Kurt Anstreicher and computer science doctoral student Nathan Brixius accomplished, after nearly 24 months, what no one else could in 32 years.

They beat the "NUG30."

"It has resisted solution attempts for over 30 years now, so for that reason, it's quite a breakthrough," said Jeff Linderoth, a researcher at Argonne National Lab in Illinois and part of the team. "It's not like this is a cure for cancer or anything, but it's important."

For those who regularly spend time dwelling on quadratic assignment problems, the pesky one they solved is known as NUG30, named after a researcher named Nugent.

NUG30 was first posed in 1968 as a test of computer capabilities, but it had remained unsolved because of its complexity.

The problem involves assigning 30 facilities to 30 fixed locations so as to minimize the total cost of transferring material between the facilities.

In simple terms, the problem was like finding the best way to arrange departments within a hospital so that patients don't need to travel farther than necessary.

It took the help of more than 1,000 computers (an average of 650 at once) from eight institutions around the world processing for nearly seven days to solve the little bugger, Linderoth said.

The group, which also included Jean-Pierre Goux of the Argonne National Lab, solved the puzzle two weeks ago.

If a single computer had run the problem, the researchers estimate, it would have taken nearly seven years to solve.

The U of I researchers developed the necessary math software and the Illinois researchers developed a system to coordinate all of the computers using a University of Wisconsin program called Condor.