Sampling methods for multi-stage robust optimization problems

In this paper, we consider multi-stage robust optimization problems of the minimax type. We
assume that the total uncertainty set is the cartesian product of stagewise compact uncertainty
sets and approximate the given problem by a sampled subproblem. Instead of looking for
the worst case among the infinite and typically uncountable set of uncertain parameters, we
consider only the worst case among a randomly selected subset of parameters. By adopting
such a strategy, two main questions arise: (1) Can we quantify the error committed by the
random approximation, especially as a function of the sample size? (2) If the sample size
tends to infinity, does the optimal value converge to the “true” optimal value? Both questions
will be answered in this paper. An explicit bound on the probability of violation is given
and chain of lower bounds on the original multi-stage robust optimization problem provided.
Numerical results dealing with a multi-stage inventory management problem show that the
proposed approach works well for problems with two or three time periods while for larger
ones the number of required samples is prohibitively large for computational tractability.
Despite this, we believe that our results can be useful for problems with such small number
of time periods, and it sheds some light on the challenge for problems with more time periods.