Bounding the optimal number of policies for robust K-Adaptability
研究了在鲁棒优化中，两阶段问题达到最优解所需的最小策略数量k的界限，给出了凸不确定集下的线性或指数依赖关系，并证明了有限集下计算最小k是NP难的。
Abstract In the realm of robust optimization the k -adaptability approach is one promising method to derive approximate solutions for two-stage robust optimization problems. Instead of allowing all possible second-stage decisions, the k -adaptability approach aims at calculating a limited set of k such decisions already in the first-stage before the uncertainty is revealed. The parameter k can be adjusted to control the quality of the approximation. However, not much is known on how many solutions k are needed to achieve an optimal solution for the two-stage robust problem. In this work we derive bounds on k which guarantee optimality for general non-linear problems with integer decisions where the uncertainty appears in the objective function or in the constraints. For convex uncertainty sets we show that for objective uncertainty the bound depends linearly on the dimension of the uncertainty, while for constraint uncertainty the dependence can be exponential, still providing the first generic bound for a wide class of problems. Additionally, we provide approximation guarantees if k is smaller than the derived bounds. The results give new insights on how many solutions are needed for problems as the decision dependent information discovery problem or the capital budgeting problem with constraint uncertainty. Finally, for finite uncertainty sets we show that calculating the minimal k for which k -adaptable and two-stage problems are equivalent is NP-hard and derive a greedy method which approximates this k for the case where no first-stage decisions exist.