CONTACT: GARY GALLUZZO
300 Plaza Centre One
Iowa City IA 52242
(319) 384-0009; fax (319) 384-0024
Release: Oct. 12, 2001
UI professor wins again, solves 40-year-old mathematics problem
University of Iowa researcher has helped solve an applied mathematics problem
that had challenged computer scientists for 40 years, just one year after
he helped find the solution to a 32-year-old problem.
Kurt Anstreicher, professor of management sciences in the Henry B. Tippie
College of Business, working with Nathan Brixius, who earned his doctoral
degree in computer science from the UI in 2000, discovered how to link 34
computer components together on a 9-by-4 grid using the shortest-possible
wiring scheme. The problem, formally know as "ste36a" and based on the design
of a UNIVAC computer, was posed by researcher Leon Steinberg in 1961. The
solution to the problem was scheduled to be presented at a Friday, Oct. 12
mathematics workshop held in Berlin, Germany.
Anstreicher says that because there are only 36 possible locations for
components, with a total of 2,625 connections between them, the wiring problem
may not seem very difficult. However, the number of possible solutions is
about "5E40," or the number represented by the number 5 followed by 40 zeros.
The algorithm that solved the problem considered about 1.8 billion sub-problems
and required about 18 days running on a single 800-megahertz personal computer.
"This may sound like a lot, but it is in fact much less time than anyone
would ever have thought possible," Anstreicher says. In the summer of 2000
Anstreicher, Brixius, and colleagues from Argonne National Lab used an average
of 650 computers for a week to solve the "nug30" problem, posed in 1968. "People
who work on such problems thought that the wiring problem would be harder
to solve than nug30, but it turned out to be much easier," says Anstreicher.
"We learned techniques in the course of solving nug30 that were very effective
in speeding up the solution of Steinberg's problem."
Like the nug30 problem, the wiring problem is a "quadratic assignment
problem," or QAP. Such problems arise in the field of location theory, and
are known to be extremely difficult to solve. Other applications of QAPs include
designing computer chips, and arranging departments within a hospital so as
to minimize the total distance that patients must travel between them.
Brixius, a Cedar Falls native who works for Microsoft Corporation in Redmond,
Wash., says the knowledge he gains from such projects helps him in his work
developing project management and scheduling software. "Microsoft is not in
the business of solving 40-year-old wiring problems, but there are underlying
similarities between ste36a and many scheduling problems," says Brixius. "The
techniques we used to solve Steinberg's problem can be adapted to help solve
problems I encounter in my day-to-day work."
Looking to the future, Anstreicher says, "Problems like nug30 and ste36a
were, until very recently, considered intractable. With continued improvements
in algorithms and hardware, solving them could be commonplace in the not-too-distant
future." Adds Brixius, "I am hopeful that our work will inspire further research
that leads to even better methods for taking on difficult problems in this