In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such ”infinite” problems are practically impossible to solve as they are formulated and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e. finite tree models, for which the optimal values give upper and lower bounds for the optimal values of the original infinite problem. Typically, there is a gap between the lower and upper bound. However, this gap can be made arbitrarily small by making the approximating trees bushier. We consider approximations in the first order stochastic sense, in the convex order sense and based on subgradient approximations. Their use is shown in a multistage risk-averse production problem.
Citation
Under Evaluation. Submitted to SIOPT on July 25 2017