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

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.

Automated summary

A computational method is developed to solve time consistent distributionally robust multistage stochastic linear programs with discrete distribution using nested Benders decomposition. The method approximates the cost-to-go function at each node through backward steps solving conic programming problems, and generates additional trial points through forward steps. A new convergence analysis framework is established to ensure global convergence, independent of the assumption of polyhedral structure.