On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems
On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems
复制标题
DOI：
10.1287/moor.1090.0440
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
D. Bertsimas;Vineet Goyal
中科院分区：
文献类型：
--
作者：
D. Bertsimas;Vineet Goyal
我们考虑一个两阶段的混合整数随机优化问题，并表明一个静态的鲁棒解决方案是一个很好的近似完全适应两阶段的随机问题的解决方案，在相当一般的假设下的不确定性集和概率分布。特别是，我们表明，如果右手边的约束是不确定的，属于一个对称的不确定性集（如超立方体，椭球或范数球）和概率测度也是对称的，那么相应的鲁棒问题的最优固定解的成本最多是两阶段随机问题的最优期望成本的两倍。此外，我们证明了界是紧对称的不确定性集，可以是任意大的，如果不确定性集是不对称的。我们把鲁棒问题的最优代价与两阶段随机问题的最优代价之比称为随机性缺口。我们还扩展了另一类不确定性集称为积极的随机差距的界限。如果目标系数和右手边都是不确定的，我们表明，随机性差距可以任意大，即使不确定性集和概率测度都是对称的。然而，我们证明了适应性差距（鲁棒问题的最优成本和两阶段完全适应性问题的最优成本之比）是最多4，即使目标系数和右侧的约束是不确定的，属于对称不确定性集。这个界也适用于正不确定集的类。此外，如果不确定性集是一个超立方体（对称集的特殊情况），适应性差距是一个更一般的不确定性模型，其中的约束系数也是不确定的。
We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the two-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive. If both the objective coefficients and right-hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a two-stage fully adaptable problem) is at most four even if both the objective coefficients and the right-hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain.