A new upper bound for the multiple knapsack problem
From MaRDI portal
Publication:6350846
DOI10.1016/J.COR.2021.105210arXiv2010.04187MaRDI QIDQ6350846FDOQ6350846
Authors: Paolo Detti 
Publication date: 8 October 2020
Abstract: 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.
This page was built for publication: A new upper bound for the multiple knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350846)
