Decomposing the mean risk problem: a Lagrangian Relaxation approach and its comparison with the Benders decomposition algorithm

In this paper we consider the mean risk problem and formulate two alternative decomposition methods for it. The mean risk problem is a stochastic problem where the scenarios are tangled by the risk constraints. Apart from other possible scenario-coupling constraints like the typical ones derived from modeling the non-anticipative criterion of the stochastic optimization problem, the set of constraints introduced to model the risk can increase notably the dificulty of the resulting problem. The objective of this paper is to find a decomposition procedure where such dificulty can be alleviated. The paperpresents a general framework to decompose the mean risk problem by both the Lagrangian Relaxation and the Benders decomposition methods. The particularities of each decomposition method are studied in detail, and the comparison and equivalence between them is established in terms of their Master and Sub-problem mathematical formulations. The paper presents a stylised example case to highlight the applicability of both approaches with an special emphasis on the Lagrangian Relaxation as it allows to treat the mean risk problem as a risk-neutral problem by substituting the original scenario probabilities by the risk-adjusted ones.