Accelerating techniques on nested decomposition

Abstract

In this paper, we consider the nested decomposition method in the context of multistage stochastic problems with scenario trees where we contribute with improvements in accelerating convergence to optimum. We first propose a hybrid protocol for transmitting cuts across nodes aiming at a trade-off between the inherent benefits and drawbacks of the single (aggregated) versus multi-cut (desegregated) versions. The idea we aim to explore is to reduce the size of the problem solved at each iteration by applying the aggregated version of the cuts on the furthest nodes of the tree. We then turn our attention towards the selection of first-stage solutions by employing sampling and simulation aiming to carefully choose those first-stage solution that are potentially capable to drastically decrease the gap between the upper and lower bound at each iteration. The problems on which the latter technique is applied present a special structure, according to which the first-stage variables are linked to all further stages. We test both accelerating techniques on a generic problem which displays a blend of two-stage and multistage structure and we report significant savings in terms of CPU time and number of iterations to convergence. © 2016 Informa UK Limited, trading as Taylor & Francis Group.