Optimizing a world of uncertainty

Investors trying to predict the stock market, farmers fretting over the weather, national security officials anticipating a terrorist attack - the amount of uncertainty in the world can seem daunting.
Not to Jeff Linderoth.
Linderoth, an assistant professor of industrial and systems engineering, marshals the world's most powerful computers to tackle problems with millions of variables and possible outcomes.
Linderoth recently received an Early Career Award from the U.S. Department of Energy (DOE) to solve large-scale numerical optimization problems characterized by high levels of uncertainty.
He will tackle these complex problems, which affect environmental planning, national security and many other areas, in two steps. First, he will develop algorithms, or precise sets of rules specifying how to solve problems. Next, he will convert the algorithms into software programs that use computational grids - groups and networks of computers whose collective capacities are harnessed. These grids can be used to solve large-scale problems that would overwhelm a single computer.
Linderoth's award, which runs for three years and is administered by DOE's Mathematical, Information and Computational Sciences Division, is titled Optimization Under Nonconvexity and Uncertainty: Algorithms and Software.
Engineers use the term stochastic optimization to describe their efforts to optimize systems containing numerous random variables. The word stochastic is derived from a Greek word meaning to guess at.
Stochastic optimization problems require engineers to take into account two classes of variables, says Linderoth. Decision variables can be controlled. Random variables cannot be.
One example of a stochastic optimization problem, says Linderoth, is the effort by the federal government to intercept illegal drugs flowing into the U.S.
The government has a fixed budget to make it more difficult for the drug smugglers to travel through the network, or border, says Linderoth. The uncertainty comes into play when, even if we choose to beef up a part of the network by installing sensors, we don't know if the sensors will detect the drugs. The goal is to design a system that is robust with respect to these failures, and will, in the long run, catch as many smugglers as possible.
Linderoth will also help DOE with mixed-integer nonlinear programming problems (nonconvex optimization), which involve discrete, yes-or-no types of decisions as well as nonlinear elements that have a continuum of random values.
The design and installation of a gas pipeline network, says Linderoth, requires engineers to make both types of decisions. The location of pipes and compressors requires discrete decisions, while calculating the optimal flow of natural gas is a nonlinear problem.
All the software Linderoth develops will be made available via The Network-Enabled Optimization System (NEOS), a server established 10 years ago to help engineers, scientists, students and business people solve optimization problems remotely over the Internet. Some of the problems people submit to NEOS are solved using computational resources and software at Lehigh.
Linderoth has made a name for himself in supercomputing and the development of a national computational grid. From 1998 to 2000, he was a visiting scientist at Argonne National Laboratory in Chicago, which has done much of the conceptual and software-design work in grid computing. He was named the Enrico Fermi Scholar at Argonne in 1999.
Linderoth was a member of the Argonne and University of Iowa team that solved the nug30 Quadratic Assignment Problem, a complex facility-location problem that had been unsolved for over 30 years. The computation took one week of calendar time and 11 years of CPU time, as 653 machines participated.
Two years ago, Linderoth and a colleague from the University of Wisconsin-Madison received a grant from the National Science Foundation through its National Middleware Initiative (NMI). NMI links separate applications across the Internet or across local area networks to create a grid where users share computers, data and other distributed resources.
A goal of NMI and similar initiatives is to shift unused power from idle or under-utilized computers to a grid whose online users tackle computational problems that require large amounts of capacity.
Linderoth's goal with the NSF project is to develop Master-Worker, a reliable, easy-to-use software tool that can execute complex numerical algorithms on computational grids and can be easily integrated with other NMI middleware.
Linderoth supervises six graduate students and collaborates with researchers at Argonne and Sandia National Laboratories, and with university colleagues from Carnegie Mellon, Georgia Tech, Wisconsin-Madison, and Northwestern. He and Rosemary Berger and Ted Ralphs, fellow assistant professors of industrial and systems engineering at Lehigh, have created the Computational Optimization Research@Lehigh, or COR@L Lab. COR@L, housed in Mohler Lab, is a research group focused on the computational issues involved in modeling and solving large-scale optimization problems.