Optimization Online


Stochastic Decomposition for Two-stage Stochastic Linear Programs with Random Cost Coefficients

Harsha Gangammanavar(harsha***at***smu.edu)
Yifan Liu(imliuyifan***at***gmail.com)
Suvrajeet Sen(sen***at***datadrivendecisions.org)

Abstract: Stochastic decomposition (SD) has been a computationally effective approach to solve large-scale stochastic programming (SP) problems arising in practical applications. By using incremental sampling, this approach is designed to discover an appropriate sample size for a given SP instance, thus precluding the need for either scenario reduction or arbitrary sample sizes to create sample average approximations (SAA). SD provides solutions of similar quality in far less computational time using ordinarily available computational resources. However, previous versions of SD did not allow randomness to appear in the second-stage cost coefficients. In this paper, we extend its capabilities by relaxing this assumption on cost coefficients in the second-stage. In addition to the algorithmic enhancements necessary to achieve this, we also present the details of implementing these extensions which preserve the computational edge of SD. Finally, we demonstrate the results obtained from the latest implementation of SD on a variety of test instances generated for problems from the literature. We compare these results with those obtained from the regularized L-shaped method applied to the SAA function with different sample sizes.

Keywords: Stochastic programming, stochastic decomposition, sample average approximation, two-stage models with random cost coefficients, sequential sampling.

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/06/2018
Entry Accepted: 10/07/2018
Entry Last Modified: 10/06/2018

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