The robust knapsack problem with queries
The robust knapsack problem with queries
复制标题
查询的鲁棒背包问题
DOI：
10.1016/j.cor.2014.09.010
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Schöbel
中科院分区：
文献类型：
--
作者：
Goerigk;Schöbel
我们考虑了项目权重不确定的鲁棒背包问题。我们被允许查询一项以找到其确切的权重，其中此类查询的数量受给定参数Q的限制。在进行这些查询后，我们需要对项目进行稳健的包装，即对于项目权重的所有剩余可能情景，项目的选择是可行的。我们考虑的中心问题是：为了获得最大利润，应该查询哪些项目？我们引入了严格健壮性查询竞争性的概念来评价算法的质量，并得到了基于区间不确定性的竞争性的下界和上界。类似于在线算法的研究，我们研究了不同框架下的竞争力，即确定性算法的最坏情况查询竞争力、随机化算法的期望查询竞争力以及不确定输入数据的已知分布的平均案例竞争力。我们推导了这些不同框架的理论界限，并在实验中对它们进行了评估。我们还将该方法推广到Bertsimas和Sim.引入的Γ约束不确定性问题，并给出了求解该问题的启发式算法。在考虑区间不确定性和Γ约束不确定性的计算实验中，我们评估了它们的经验性能。虽然使用Γ限制的不确定性提高了解决方案的名义性能(正如预期的那样)，但我们发现查询竞争力变得更差。
We consider robust knapsack problems where item weights are uncertain. We are allowed to query an item to find its exact weight,where the number of such queries is bounded by a given parameterQ. After these queries are made, we need to pack the items robustly, i.e., so that the choice of items is feasible for every remaining possible scenario of item weights.The central question that we consider is: Which items should be queried in order to gain maximum profit? We introduce the notion ofquery competitivenessfor strict robustness to evaluate the quality of an algorithm for this problem, and obtain lower and upper bounds on this competitiveness for interval-based uncertainty. Similar to the study of online algorithms, we study the competitiveness under different frameworks, namely we analyze the worst-case query competitiveness for deterministic algorithms, the expected query competitiveness for randomized algorithms and the average case competitiveness for known distributions of the uncertain input data. We derive theoretical bounds for these different frameworks and evaluate them experimentally. We also extend this approach toΓ-restricted uncertainties introduced by Bertsimas and Sim.Furthermore, we present heuristic algorithms for the problem. In computational experiments considering both the interval-based and theΓ-restricted uncertainty, we evaluate their empirical performance. While the usage of aΓ-restricted uncertainty improves the nominal performance of a solution (as expected), we find that the query competitiveness gets worse.
登录
查看更多内容
计算具有不确定性的中位数
影响因子：
1
作者：
T. Feder;R. Motwani;R. Panigrahy;Christopher Olston;J. Widom
通讯作者：
J. Widom
计算具有不确定性的最短路径
DOI：
10.1016/j.jalgor.2004.07.005
发表时间：
2003
期刊：
J. Algorithms
影响因子：
--
作者：
T. Feder;R. Motwani;Liadan O'Callaghan;Christopher Olston;R. Panigrahy
通讯作者：
R. Panigrahy
具有不确定目标系数的线性规划的信息收集
影响因子：
3.1
作者：
I. Ryzhov;Warrren B Powell
通讯作者：
Warrren B Powell
关于鲁棒背包问题
影响因子：
3.1
作者：
M. Monaci;U. Pferschy
通讯作者：
U. Pferschy
多场景背包问题最大最小优化的启发式精确算法
影响因子：
4.6
作者：
Fumiaki Taniguchi;Takeo Yamada;S. Kataoka
通讯作者：
S. Kataoka