In this paper we show that when a multistage stochastic problem with stage-wise independent realizations has only RHS uncertainties, solving one tree provides a valid lower bound for all trees with the same number of scenarios per stage without any additional computational effort. The only change to the traditional algorithm is the way cuts are calculated. Once the first tree is solved approximately, the inference of the statistical significance of the current number of scenarios per stage is performed solving for each new tree sampled an easy LP to get a lower bound for the new tree that is often tight. The result of the inference are fast estimates of the mean, variance and max variation of lower bounds across many trees. If the variance of the calculated lower bounds is small, we declare the true SDDP problem well approximated because the cutting planes model has a small sensitivity to the trees sampled. Otherwise, we increase the number of scenarios per stage and repeat. We do not make assumptions on the distributions of the random variables. The results are not asymptotic. Our method has applications to the determination of the correct number of scenarios per stage. The stage-wise independence assumption can be dropped as well as the constraint of having only RHS uncertainties. However, the sensitivity of the optimal value with respect to the tree is only for the RHS vectors. Extensions for uncertainties in the objective only are possible via the dual SDDP. We test our method numerically and the computational results are sound.
Article
View Cut-Sharing Across Trees and Efficient Sequential Sampling for SDDP with Uncertainty in the RHS