(485d) Mixed Integer Linear Programming Formulation of Value at Risk and Conditional Value at Risk for General Stochastic Programs

Introduction While minimizing the expected value is often the primary objective of stochastic programs, risk considerations are often an important secondary objective. Risk is a broad term that can refer to many aspects, including standard deviation of the profit distribution, expected loss in cases of failure or even the maximum amount of money that can be committed to a project. In this talk we will focus on two of the more common risk metrics Value at Risk (VaR) and Conditional Value at Risk (CVaR).

Background VaR is merely the α-quantile of the return distribution function and has gained significant literature review particularly in the financial community. While prominent, this measure is not sub-additive and hence not a coherent risk measure. In response to this, the concept of CVaR was developed, which is the expected value of the worst range of scenarios.

In stochastic programming, the calculation of both VaR and CVaR require the knowledge of which scenario represents the α-quantile. In the development of CVaR, Rockafellar and Uryasev (2002) assumed that the scenarios could be ordered and this approach remains common within the literature. In other approaches, such as the one proposed by Benati and Rizzi (2007), VaR is calculated after parameter estimation of the distribution and fixed as a parameter to be optimized. While useful if additional information about the problem or scenarios is available, this is not always the case and we desire a formulation that can be more generally applied.

Problem We assume that the problem is defined by discrete scenarios with known probability. Additionally we assume that the objective function of each scenario can be calculated, with the overall objective being the expected value of the scenario objectives. The goal is to calculate VaR and CVaR of the problem, either for use in the objective or constraints. When the VaR/CVaR is in the objective function, we additionally assume that the problem is solved to optimality.

Probabilistic risk management techniques provide an initial approach to calculating the VaR. Rather than setting the risk threshold as a parameter, we allow it to change as a variable. When placed in the objective, the probabilistic constraint is sufficient to provide a unique value in the optimal solution, providing the VaR. To calculate the CVaR, we build upon the work of Schultz and Tiedemann (2006), again with the risk threshold treated as a variable rather than a parameter. Even though the threshold appears as a variable in the objective the VaR is not guaranteed to be found even if the CVaR is accurate.

When the VaR/CVaR does not appear in the objective, there is nothing to prevent artificially high values from being assigned to the variables. In this case, it is necessary to introduce a second set of indicator variables constraining their values. Because these are highly related to the initial probabilistic constraints, we developed a set of tightening constraints leading to similar computation times as when VaR and CVaR appeared in the objective.

Conclusions We are able to calculate both the VaR and CVaR for stochastic programs with unordered scenarios and no information regarding the underlying uncertainty beyond scenario probabilities using mixed integer linear programming. Additionally, the computational requirements of the proposed methods were found to be comparable to probabilistic risk constraints in test examples.

Benati, S. and R. Rizzi (2007) A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem. European Journal of Operational Research. 176: 423-434. Rockafellar, R. T. and S. Uryasev (2002). Conditional value-at-risk for general loss distributions. Journal of Banking & Finance 26(7): 1443-1471. Schultz, R. and S. Tiedemann (2006). Conditional value-at-risk in stochastic programs with mixed-integer recourse. Mathematical Programming 105(2-3): 365-386.