Optimization Online


Optimization Driven Scenario Grouping

Kevin Ryan (kryan31***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Deepak Rajan (rajan3***at***llnl.gov)

Abstract: Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves upon these bounds by re-enforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into 'groups'. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present a mixed integer programming formulation. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness for solving standard test instances of two-stage 0-1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

Keywords: stochastic programming, scenario reduction

Category 1: Stochastic Programming

Category 2: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 03/10/2016
Entry Accepted: 03/11/2016
Entry Last Modified: 05/04/2016

Modify/Update this entry

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


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society