Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound
by Vincent Boyer, Didier El Baz, Moussa Elkihel
European J. of Industrial Engineering (EJIE), Vol. 4, No. 4, 2010

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]

Online publication date: Fri, 01-Oct-2010

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the European J. of Industrial Engineering (EJIE):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com