Title: Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound

Authors: Vincent Boyer, Didier El Baz, Moussa Elkihel

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

Abstract: This article presents an exact cooperative method for the solution of the multidimensional knapsack problem (MKP) which combines dynamic programming and branch and bound. Our method makes cooperate a dynamic programming heuristics based on surrogate relaxation and a branch and bound procedure. Our algorithm was tested for several randomly generated test sets and problems in the literature. Solution values of the first step are compared with optimal values and results provided by other well-known existing heuristics. Then, our exact cooperative method is compared with a classical branch and bound algorithm. [Received 8 October 2008; Revised 28 May 28 2009; Revised 10 December 2009; Accepted 11 December 2009]

Keywords: multidimensional knapsack problems; cooperative methods; cooperation; dynamic programming; branch and bound; heuristics; surrogate relaxation; genetic algorithms; random generation; test sets; solution values; optimal values; optimisation.

DOI: 10.1504/EJIE.2010.035653

European Journal of Industrial Engineering, 2010 Vol.4 No.4, pp.434 - 449

Published online: 01 Oct 2010 *

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