Parallel Scenario Decomposition of Risk-Averse 0-1 Stochastic Programs

Yan Deng (), Shabbir Ahmed () and Siqian Shen ()
Additional contact information
Yan Deng: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Shabbir Ahmed: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Siqian Shen: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 90-105

Abstract: In this paper, we extend a recently proposed scenario decomposition algorithm for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider two-stage 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 overhead 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 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0767 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:90-105

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().