Multi-stage dynamic optimization is widely applicable as most real- world problems can be formulated as multi-stage decision making problems under uncertainty. However, such formulations are usually computationally intractable even for two-stage models.
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 geometric properties of the uncertainty sets. In particular, we show that a class of robust and finitely adaptable solutions is a good approximation for both the multi-stage stochastic as well as the adaptive optimization problem and the performance ratio depends on geometric properties such as symmetry of the uncertainty set.
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 the past stages. Therefore, it is a tractable approximation to a fully- adaptable solution for the multi-stage problems. Our result is highly surprising as the robust approach is usually believed to be highly conservative and thus, not relevant in practice. 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.
This is based on joint work with Dimitris Bertsimas and Andy Sun.
Copyright. All Rights Reserved.