Solving some multistage robust decision problems with huge implicitly defined scenario trees

This paper describes models and solution algorithms for solving robust multistage decision problems under a special type of uncertainty model referred to here as parsimonious. The main interest of such a model is to provide compact representations of potentially huge scenario trees, leading to efficient dynamic programming-based computation of optimal strategies. Also, contrary to the case of most previously published work on similar problems, which essentially require an independence assumption (on the occurrences of uncertain events in different time periods) our model handles- and properly exploits- some form of dependence over time via a concept of uncertainty budget constraints. Examples of application are discussed including optimal inventory management and the search for robust shortest paths in directed acyclic graphs. Computational results illustrating and validating the proposed approach are also presented. Key words: robust optimization, robust dynamic programming, uncertainty models, multistage decision models, inventory management