论文标题
可回收的强大代表选择问题与离散预算不确定性
Recoverable Robust Representatives Selection Problems with Discrete Budgeted Uncertainty
论文作者
论文摘要
可恢复的强大优化是一种多阶段方法，在揭示不确定的成本方案后，可以调整第一阶段解决方案。我们分析了一类选择问题的方法。目的是从几个不相交的集合中选择固定数量的项目，以便采取恢复措施后的最差案例成本尽可能小。不确定性被建模为离散预算集，对手可以增加固定数量的项目的成本。虽然以前已经研究过此问题的特殊情况，但其复杂性仍然开放。在这项工作中，我们为缩小这一差距做出了一些贡献。我们表明该问题是NP硬化，并确定在多项式时间内仍可以解决的特殊情况。我们提供紧凑的混合式编程配方和另外两种扩展配方。最后，提供了比较不同精确溶液方法的效率的计算结果。
Recoverable robust optimization is a multi-stage approach, where it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this approach for a class of selection problems. The aim is to choose a fixed number of items from several disjoint sets, such that the worst-case costs after taking a recovery action are as small as possible. The uncertainty is modeled as a discrete budgeted set, where the adversary can increase the costs of a fixed number of items. While special cases of this problem have been studied before, its complexity has remained open. In this work we make several contributions towards closing this gap. We show that the problem is NP-hard and identify a special case that remains solvable in polynomial time. We provide a compact mixed-integer programming formulation and two additional extended formulations. Finally, computational results are provided that compare the efficiency of different exact solution approaches.
