首页|Recoverable robust representatives selection problems with discrete budgeted uncertainty
Recoverable robust representatives selection problems with discrete budgeted uncertainty
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Recoverable robust optimization is a multi-stage approach, in which 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.(c) 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
Robustness and sensitivity analysisRobust optimizationDiscrete budgeted uncertaintyCombinatorial optimizationSelection problemsSPANNING TREE PROBLEMOPTIMIZATION PROBLEMSINTERVAL UNCERTAINTYMIN-MAXAPPROXIMABILITYCOMPLEXITYALGORITHM
NSTL
Elsevier
