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

Vincent Boyer, Didier El Baz and Moussa Elkihel

European Journal of Industrial Engineering, 2010, vol. 4, issue 4, 434-449

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. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=35653 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:4:y:2010:i:4:p:434-449

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().