Optimization Online


Bounds on Risk-averse Mixed-integer Multi-stage Stochastic Programming Problems with Mean-CVaR

Ali Irfan Mahmutogullari(a.mahmutogullari***at***bilkent.edu.tr)
Ozlem Cavus(ozlem.cavus***at***bilkent.edu.tr)
M. Selim Akturk(akturk***at***bilkent.edu.tr)

Abstract: Risk-averse mixed-integer multi-stage stochastic programming forms a class of extremely challenging problems since the problem size grows exponentially with the number of stages, the problem is non-convex due to integrality restrictions and the objective function is a dynamic measure of risk. For this reason, we propose a scenario tree decomposition approach, namely group subproblem approach, to obtain bounds for such problems with an objective of dynamic mean-CVaR risk measure. Our approach does not require any special problem structure such as convexity and linearity, therefore it can be applied to a wide range of problems. We obtain lower bounds by using different convolution of mean-CVaR risk measures and different scenario partition strategies. The upper bounds are obtained through the use of optimal solutions of group subproblems. Using these lower and upper bounds, we propose an algorithm for risk-averse mixed-integer multi-stage stochastic problems with mean-CVaR risk measures. We test the performance of the proposed algorithm on a multi-stage stochastic lot sizing problem and compare different choices of lower bounds and partition strategies. Comparison of the proposed algorithm and the commercial solver revealed that, on the average, the proposed algorithm yields 2.58 times stronger bounds compared to a commercial solver.

Keywords: Mixed-integer multi-stage stochastic programming; Dynamic measures of risk; CVaR; Bounding

Category 1: Stochastic Programming


Download: [PDF]

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