Scenario cluster Lagrangean decomposition for risk averse in multistage stochastic optimization

In this work we present a decomposition approach as a mixture of dualization and Lagrangean Relaxation for obtaining strong lower bounds on large-sized multistage stochastic mixed 0-1 programs with a time stochastic dominance risk averse measure. The objective function to minimize is a composite function of the expected cost along the time horizon over the scenarios and the penalization of the expected cost excess on reaching the set of thresholds under consideration, subject to a bound on the expected cost excess for each threshold and a bound on the failure probability of reaching it. The main differences with some other risk averse strategies are presented. The problem is represented by a mixture of the splitting representation up to a given stage, so-called break stage, and the compact representation for the other stages along the time horizon. The dualization of the nonanticipativity constraints for the node-based and risk averse variables up to the break stage and the Lagrangean Relaxation of the cross node constraints of the risk averse strategy result in a model that can be decomposed into a set of independent scenario cluster submodels. Three Lagrangean multipliers updating schemes as the Subgradient method, the Lagrangean Progressive Hedging algorithm and the Dynamic Constrained Cutting Plane are computationally compared. We have observed in the randomly generated instances we have experimented with that the smaller the number of clusters, the stronger the lower bound provided for the original problem (even, frequently, it is the solution value) obtained with an affordable computing time.