The routing of automobile traffic and the management of a stock portfolio both involve optimization — using a mathematical model to increase the efficiency of a complex system with many components, variables and input parameters.
Ted Ralphs, associate professor of industrial and systems engineering, writes optimization software that can be customized to a variety of applications. He attempts to accelerate optimization by applying more efficient computing power and using multiple processors and parallel computers in tandem.
“I deal with difficult problems that have a very large space of possibilities,” Ralphs says. “Searching through that space is the key. You cannot search efficiently by merely rating all the possibilities and determining which is best. There are too many possibilities. The efficient use of computing power is paramount.”
The task for Ralphs might seem simple — segment the search space into smaller pieces and assign a single processor to each. But many of these tiny segments “contain nothing of interest,” leaving too many processors with nothing important to do.
The solution, he says, lies in sharing information between processors.
“If one processor is doing something that seems interesting, it has to be able to note that and hand it off to another processor. Doing that efficiently is the challenge.”
Ralphs, who has developed software packages to solve large-scale optimization problems, chairs the Technical Leadership Council of an open source software foundation called COIN-OR. He has attracted funding from NSF, IBM, the Commonwealth of Pennsylvania and the U.S. Army.
