-

 

 

 




Optimization Online





 

PySP: Modeling and Solving Stochastic Programs in Python

Jean-Paul Watson(jwatson***at***sandia.gov)
David Woodruff(dlwoodruff***at***ucdavis.edu)
William Hart(wehart***at***sandia.gov)

Abstract: Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One key factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of deterministic models, which are often formulated first. A second key factor relates to the difficulty of solving stochastic programming models, particularly the general mixed-integer, multi-stage case. Intricate, configurable, and 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 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. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.

Keywords: Stochastic programming, software, decomposition methods, algebraic modeling language

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems (Modeling Languages and Systems )

Category 3: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Citation: Technical Report, Sandia National Laboratories, August, 2010.

Download: [PDF]

Entry Submitted: 09/08/2010
Entry Accepted: 09/08/2010
Entry Last Modified: 09/08/2010

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society