Bounding Multistage Stochastic Programs: A Scenario Tree Based Approach

Multistage mixed-integer stochastic programs are among the most challenging optimization problems combining stochastic programs and discrete optimization problems. Approximation techniques which provide lower and upper bounds to the optimal value are very useful in practice. In this paper we present a critic summary of the results in Maggioni et al., J Optim Theory Appl 163:200–229 (2014), [4] and in Maggioni et al., Comput Manag Sci 13:423–457 (2016), [5] where we consider bounds based on the assumption that a sufficiently large discretized scenario tree describing the problem uncertainty is given but is unsolvable. Bounds based on group subproblems, quality of the deterministic solution and rolling-horizon approximation will be then discussed and compared.