论文标题
双标准的双背包问题与分组项目
Bi-Criteria Multiple Knapsack Problem with Grouped Items
论文作者
论文摘要
分组项目的多个背包问题旨在通过考虑背包的能力来通过在多个背包中分配一组项目来最大化奖励。一个组中的所有项目均已分配，或者根本没有分配。我们提出的算法可以保证奖励不小于最佳解决方案，并且具有超过的背包能力。为了获得容量可比性的解决方案，我们提出了一种二进制搜索启发式，并结合了这些算法。我们在一组随机生成的实例中测试了算法和启发式方法的性能，并表明它们既有效又有效，即它们运行速度相当快，并生成了高质量的解决方案。
The multiple knapsack problem with grouped items aims to maximize rewards by assigning groups of items among multiple knapsacks, considering knapsack capacities. Either all items in a group are assigned or none at all. We propose algorithms which guarantee that rewards are not less than the optimal solution, with a bound on exceeded knapsack capacities. To obtain capacity-feasible solutions, we propose a binary-search heuristic combined with these algorithms. We test the performance of the algorithms and heuristics in an extensive set of experiments on randomly generated instances and show they are efficient and effective, i.e., they run reasonably fast and generate good quality solutions.
