Robust combinatorial optimization with knapsack uncertainty
Robust combinatorial optimization with knapsack uncertainty
复制标题
DOI：
10.1016/j.disopt.2017.09.004
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
M. Poss
中科院分区：
文献类型：
--
作者：
M. Poss
本文研究了由背包约束定义的不确定多面体在优化变量空间和扩展空间中的最小最大鲁棒组合优化问题。我们提供了精确和近似算法，扩展了Bertsimas和Sim（2003）提出的迭代算法。我们还研究了该方法的局限性，并指出了np困难的情况。然后，对具有背包约束的轴平行椭球体进行了逼近，并给出了相应鲁棒问题的逼近格式。该近似格式也适用于处理与轴平行的椭球体与箱体的交点。
We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertsimas and Sim (2003). We also study the limitation of the approach and point out NP-hard situations. Then, we approximate axis-parallel ellipsoids with knapsack constraints and provide an approximation scheme for the corresponding robust problem. The approximation scheme is also adapted to handle the intersection of an axis-parallel ellipsoid and a box.