Stochastic Decomposition Algorithms for Risk-Averse Multistage Stochastic Linear Programs and Applications

Abstract

Mean-risk stochastic linear programming provides a framework for controlling cost variability in problems involving sequential decision making under uncertainty. It goes beyond the classical expected value framework by including risk measures in the objective function and aims at controlling cost variability in the solution. This allows for modeling risk averseness in variety of applications such as long-term financial planning, scheduling of power systems, supply chain management and portfolio optimization. In this dissertation, we derive stochastic decomposition algorithms for solving mean-risk twosatge stochastic linear programs (MR-SLP) and mean-risk multistage stochastic linear programs (MR-MSLP) with deviation and quantile risk measures. Stochastic decomposition(SD) is a type of internal sampling method and at every iteration of algorithm only one linear problem is solved for approximating the recourse function. A salient feature of the SD algorithm is that the number of samples is not fixed a priori, which allows to obtain good candidate solutions early in the procedure. We also report on a computational study to evaluate the empirical performance of the SD algorithms for MR-SLP and MR-MSLP with expected excess(EE), quantile deviation(QDEV) and conditional value-at-risk(CVaR) as risk measures. The goal of the study was to analyze for a given instance how SD algorithm performs across different levels of risk, investigate the effect of different risk measures and understand when it is appropriate to use the risk-averse approach. For MR-SLP, the SD algorithm is implemented and applied to standard test instances and it shows that the risk measure QDEV has more impact on expected cost and the cost associated with extreme scenarios compared to the impact of CVaR and EE. We also observed that for higher target values, the risk measure EE becomes effective only for a relatively small number of scenarios and has little to no-effect on the optimal solution for small values of the risk trade-off factor. The computational study also demonstrates that under risk aversion the rate of convergence of SD algorithm remains consistent as opposed to sample average approximation approach. For the multistage case, the SD algorithm is applied to an instance of long-term hydrothermal scheduling (LTHS) and it shows that the risk trade-off factor has a significant impact on the solution and the risk measure conditional value-at-risk exhibits a better control over the extreme scenarios at lower values of risk trade-off factor. The study also shows that the risk-neutral approach is still appropriate for the LTHS problem.