CONTACT: GARY GALLUZZO
300 Plaza Centre One
Iowa City IA 52242
(319) 3840009; fax (319) 3840024
email: garygalluzzo@uiowa.edu
Release: Oct. 12, 2001
UI professor wins again, solves 40yearold mathematics problem
A
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 32yearold 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 9by4 grid using the shortestpossible
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 subproblems
and required about 18 days running on a single 800megahertz 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 40yearold 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 daytoday 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 nottoodistant
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
area."
