A class of efficiently solvable multistage optimization problems under uncertainty and applications

We investigate a class of specially structured multistage robust optimization problems under uncertainty for which efficient computation of exact optimal robust strategies is possible. As an essential feature of this class of problems, we introduce the concept of a state-space representable uncertainty set, based on an underlying graph-theoretic structure. This concept is shown to extend several previously proposed types of uncertainty sets, and naturally lends itself to compact representations of scenario sets of huge cardinality. It is also convenient to represent uncertainty sets featuring dependence among the realizations of the uncertain parameters in successive time periods. Computational results are reported on a series of test problems featuring up to 50 time periods, in connection with an application to a multiperiod energy production planning problem. These results are shown to provide an experimental basis for comparing optimal robust strategies against optimal solutions derived from a related robust 2-stage model.