Title: A procedure-based heuristic for 0-1 Multiple Knapsack Problems

Authors: Mohamed Esseghir Lalami; Moussa Elkihel; Didier El Baz; Vincent Boyer

Addresses: CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France

Abstract: In this paper, we present a heuristic which derives a feasible solution for the Multiple Knapsack Problem (MKP). The proposed heuristic called RCH, is a recursive method that performs computation on the core of knapsacks. The RCH heuristic is compared with the MTHM heuristic of Martello and Toth. Computational results on randomly generated instances show that the proposed approach gives better gap and smaller restitution times.

Keywords: MKP; multiple knapsack problems; heuristics; dynamic programming; subset sum problem; operational research.

DOI: 10.1504/IJMOR.2012.046684

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.214 - 224

Published online: 02 May 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article