论文标题
多种背包问题的新上限
A new upper bound for the multiple knapsack problem
论文作者
论文摘要
在本文中，提出了一个新的针对多背包问题（MKP）的上限，它是基于将MKP放松到{\ em有限的顺序多重背包问题}的想法，即，一个多个knapsack问题，其中逐项大小可分开。通过适当替换具有可分割尺寸的项目的MKP实例的项目，可以获得这样一种称为顺序放松的放松。基准实例的实验结果表明，当项目数量与背包数量很小时，上限是有效的。
In this paper, a new upper bound for the Multiple Knapsack Problem (MKP) is proposed, based on the idea of relaxing MKP to a {\em Bounded Sequential Multiple Knapsack Problem}, i.e., a multiple knapsack problem in which item sizes are divisible. Such a relaxation, called sequential relaxation, is obtained by suitably replacing the items of a MKP instance with items with divisible sizes. Experimental results on benchmark instances show that the upper bound is effective when the ratio between the number of items and the number of knapsacks is small.
