c©200x INFORMS A Geometric Characterization of the Power of Finite Adaptability in Multi-stage Stochastic and Adaptive Optimization

In this paper, we show a significant role that geometric properties of uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions in multi-stage stochastic and adaptive optimiza-tion problems. We consider a fairly general class of multi-stage mixed integer stochastic and adaptive optimization problems and propose a good approximate solution policy with performance guarantees that depend on the ge-ometric properties of the uncertainty sets. In particular, we show that a class of finitely adaptable solutions is a good approximation for both the multi-stage stochastic as well as the adaptive optimization problem. A finitely adaptable solution generalizes the notion of a static robust solution and specifies a small set of solutions for each stage and the solution policy implements the best solution from the given set depending on the realization of the uncertain parameters in past stages. Therefore, it is a tractable approximation to a fully-adaptable solution for the multi-stage problems. To the best of our knowledge, these are the first approximation results for the multi-stage problem in such generality. Moreover, the results and the proof techniques are quite general and also extend to include important constraints such as integrality and linear conic constraints