Development and Implementation of Algorithms for Stochastic Integer Programming

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

This research addresses stochastic optimization problems that are further complicated by the presence of integer decision variables to model logical and other discrete decisions in a multi-period or multistage setting. To cope with the computational complexity of multistage stochastic integer optimization problems, this research will develop new methodology, algorithms, and prototype software. Fundamental properties of the value function of integer programs will be exploited in conjunction with inherent decomposability of these optimization problems in order to develop algorithms that scale well with problem size. A large number of problems in production planning and scheduling, location, transportation, finance, and engineering design require that decisions be made in the presence of uncertainty. Uncertainty, for instance, governs the prices of fuels, the availability of electricity, and the demand for chemicals. Stochastic optimization is the branch of applied mathematics that provides systematic tools to prudent decision-making under uncertainty. A key difficulty in stochastic optimization is in dealing with an uncertainty space that is huge and which leads to very large-scale optimization models. The developed algorithms will be implemented in the investigator's widely distributed global optimization package BARON and made available to the research community. If successful, this project could have profound implications in decision-making under uncertainty in many sectors of the economy.