Progressive hedging for multi-stage stochastic optimization problems
Presenters
October 19, 2010
Keywords:
- Stochastic programming
MSC:
- 90C15
Abstract
Although stochastic programming is a powerful tool for modeling decision-making under uncertainty,
various impediments have historically prevented its widespread use. One key factor involves the
ability of non-experts to easily express stochastic programming problems, ideally building on a likely
existing deterministic model expressed through an algebraic modeling language. A second key factor
relates to the difficulty of solving stochastic programming models, particularly the general mixed-integer,
multi-stage case. Intricate and configurable (and often parallel) decomposition
strategies are frequently required to achieve tractable run-times. We simultaneously address both of
these factors in our PySP software package, which is part of the COIN-OR Coopr open-source Python
project for optimization. To formulate a stochastic program in PySP, the user specifies both the
deterministic base model and the scenario tree with associated uncertain parameters in the Pyomo
open-source algebraic modeling language. Given these two models, PySP provides two general paths
for solution of the corresponding stochastic program. The first alternative involves writing the
extensive form and invoking a standard deterministic mixed-integer solver. For more complex stochastic
programs, we provide an implementation of Rockafellar and Wets' Progressive Hedging algorithm. Our
particular focus is on the use of Progressive Hedging as an effective heuristic for approximating
general multi-stage, mixed-integer stochastic programs. By leveraging the combination of a high-level
programming language (Python) and the embedding of the base deterministic model in that language
(Pyomo), we are able to provide completely generic and highly configurable solver implementations
on serial and parallel computers. PySP has been used by a number of research groups, including our own,
to rapidly prototype and solve large and difficult stochastic programming problems.