Bounds on risk-averse mixed-integer multi-stage stochastic programming problems with mean-CVaR

Ali İrfan Mahmutoğulları, Özlem Çavuş and M. Selim Aktürk

European Journal of Operational Research, 2018, vol. 266, issue 2, 595-608

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 nonlinear in general. We propose a scenario tree decomposition approach, namely group subproblem approach, to obtain bounds for such problems with an objective of dynamic mean conditional value-at-risk (mean-CVaR). 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 a solution 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 to a commercial solver revealed that, on the average, the proposed algorithm yields 1.13% stronger bounds. The commercial solver requires additional running time more than a factor of five, on the average, to reach the same optimality gap obtained by the proposed algorithm.

Keywords: Stochastic programming; Mixed-integer multi-stage stochastic programming; Dynamic measures of risk; CVaR; Bounding (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717309517
Full text for ScienceDirect subscribers only

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:eee:ejores:v:266:y:2018:i:2:p:595-608

DOI: 10.1016/j.ejor.2017.10.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().