首页> 外文期刊>INFORMS journal on computing >Heuristic and Exact Algorithms for the Interval Min-Max Regret Knapsack Problem
【24h】

Heuristic and Exact Algorithms for the Interval Min-Max Regret Knapsack Problem

机译:区间最小-最大后悔背包问题的启发式和精确算法

获取原文
获取原文并翻译 | 示例

摘要

We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in NP. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.
机译:我们考虑了0-1背包问题的一般化,其中每个项目的利润可以在以最小和最大可能利润为特征的范围内取任意值。一组特定的利润称为方案。与方案相关联的每个可行解决方案都令人遗憾,这是由该方案的最佳解决方案值与所考虑解决方案的值之间的差异给出的。然后,间隔最小-最大后悔背包问题(MRKP)将找到可行的解决方案,以使所有情况下的最大后悔最小化。从理论和实践的角度来看,这个问题都极具挑战性。它的决策版本对于多项式层次结构的第二层是完整的,因此很可能不在NP中。另外,即使计算针对场景的解决方案的遗憾也需要解决NP难题。我们研究了适用于MRKP解决方案的经典组合优化方法的行为。我们介绍了迭代的局部搜索方法和基于拉格朗日的分支剪切算法,并通过大量的计算实验评估了它们的性能。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号