Heuristic and Exact Algorithms for the Interval Min-Max Regret Knapsack Problem
Heuristic and Exact Algorithms for the Interval Min-Max Regret Knapsack Problem
复制标题
DOI：
10.1287/ijoc.2014.0632
复制
发表时间：
2015-03-01
影响因子：
2.1
通讯作者：
Yagiura, Mutsunori
中科院分区：
文献类型：
--
作者：
Furini, Fabio;Iori, Manuel;Yagiura, Mutsunori
我们考虑一个推广的0-1背包问题，其中每个项目的利润可以采取任何值的范围内的最小和最大可能的利润。一组特定的利润称为情景。每个与场景相关的可行解都有一个遗憾，由这种场景的最优解值与所考虑的解的值之间的差异给出。区间最小-最大后悔背包问题（MRKP）则是找到一个可行的解决方案，使最大遗憾在所有的情况下被最小化。这个问题无论从理论上还是实践上都极具挑战性。它的决策版本对于多项式层次的第二层是完全的，因此它很可能不在NP中。此外，即使计算一个方案的遗憾，也需要解决一个NP难题。我们研究经典的组合优化方法的行为时，适应MRKP的解决方案。我们介绍了一个迭代的局部搜索方法和拉格朗日为基础的分支和切割算法，并通过大量的计算实验评估其性能。
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.