Videos

Progressive hedging for multi-stage stochastic optimization problems

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.