Optimization Online


Parallel Scenario Decomposition of Risk Averse 0-1 Stochastic Programs

Yan Deng(yandeng***at***umich.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Siqian Shen(siqian***at***umich.edu)

Abstract: In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the considered problem. We then develop three variants of the scenario decomposition algorithm for this minimax formulation based on different relaxations of the nonanticipaticity constraints. The algorithms proceed by solving scenario subproblems to obtain candidate solutions and bounds, and subsequently cutting off the candidate solutions from the search space to achieve convergence to an optimal solution. We design three parallelization schemes for implementing the algorithms with different tradeoffs between communication time and computation time. Our computational results with risk-averse extensions of two standard stochastic 0-1 programming test instances demonstrate the scalability of the proposed decomposition and parallelization framework.

Keywords: risk-averse 0-1 stochastic programs; conditional value-at-risk (CVaR); minimax optimization; dual decomposition; distributed algorithms; parallel computing

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 01/29/2016
Entry Accepted: 01/29/2016
Entry Last Modified: 01/29/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