Parallel Scenario Decomposition of Risk-Averse 0-1 Stochastic Programs
将风险中性0-1随机规划的情景分解算法扩展到风险厌恶情形，利用对偶表示转化为极小极大问题，设计三种并行方案，在标准测试实例上验证了可扩展性。
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.