A new upper bound for the multiple knapsack problem
Paolo Detti
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 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, in terms of quality, when the ratio between the number of items and the number of knapsacks is small.
Topics & Concepts
Knapsack problemUpper and lower boundsBranch and boundMathematicsMathematical optimizationComputer scienceCombinatoricsMathematical analysisOptimization and Packing ProblemsAdvanced Manufacturing and Logistics OptimizationVehicle License Plate Recognition