A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure

Abstract

A computational method is developed for solving time consistent distributionally robust multistage stochastic linear programs with discrete distribution. The stochastic structure of the uncertain parameters is described by a scenario tree. At each node of this tree, an ambiguity set is defined by conditional moment constraints to guarantee time consistency. This method employs the idea of nested Benders decomposition that incorporates forward and backward steps. The backward steps solve some conic programming problems to approximate the cost-to-go function at each node, while the forward steps are used to generate additional trial points. A new framework of convergence analysis is developed to establish the global convergence of the approximation procedure, which does not depend on the assumption of polyhedral structure of the original problem. Numerical results of a practical inventory model are reported to demonstrate the effectiveness of the proposed method.