Mathematical models and decomposition methods for the multiple knapsack problem
Mathematical models and decomposition methods for the multiple knapsack problem
复制标题
DOI：
10.1016/j.ejor.2018.10.043
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
M. dell’Amico;Maxence Delorme;M. Iori;S. Martello
中科院分区：
文献类型：
--
作者：
M. dell’Amico;Maxence Delorme;M. Iori;S. Martello
我们考虑多背包问题，要求一组物品的最优分配，每个物品都有一个利润和一个重量，一组背包，每个背包都有一个最大的容量。这一问题涉及相关的管理问题，众所周知，在实际规模的情况下，这一问题很难解决。我们回顾了文献中的主要结果，包括一个经典的数学模型和一些改进技术。然后，我们提出了两个新的伪多项式配方，连同专门定制的分解算法，以解决实际困难的问题。大量的计算实验表明了所提出的方法的有效性。
We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.