Scalable Heuristics for Stochastic Programming with Scenario Selection

Jean-Paul Watson(jwatsonsandia.gov)
Roger J.-B. Wets(rjbwetsucdavis.edu)
David L. Woodruff(dlwoodruffucdavis.edu)

Abstract: We describe computational procedures to solve a wide-ranging class of stochastic programs with chance constraints where the random components of the problem are discretely distributed. Our procedures are based on a combination of Lagrangian relaxation and scenario decomposition, which we solve using a novel variant of Rockafellar and Wets' progressive hedging algorithm. Experiments demonstrate the ability of the proposed algorithm to quickly find near-optimal solutions -- where verifiable -- to both difficult and very large chance constrained stochastic programs using scenario decomposition. The algorithm requires orders of magnitude less time on most test instances than existing exact algorithms, and exhibits stronger scalability in terms of final solution quality on large-scale instances.

Keywords: stochastic programming, chance constraints, scenario-based decomposition, heuristics

Category 1: Stochastic Programming

Citation: Technical Report, June 2008 Discrete Math and Complex Systems Department, Sandia National Laboratories Albuquerque, NM 87185-1318

Download: [PDF]

Entry Submitted: 07/03/2008
Entry Accepted: 07/06/2008
Entry Last Modified: 07/03/2008

Modify/Update this entry