Heuristics for the 0-1 multidimensional knapsack problem Boyer, V; Elkihel, M; Baz, D. El

User activity

Share to:
View the summary of this work
Boyer, V ; Elkihel, M ; Baz, D. El
Appears In
European Journal of Operational Research
Algorithms; Business, general; Business, international
Academic; Trade
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.06.068 Byline: V. Boyer, M. Elkihel, D. El Baz Keywords: Multidimensional knapsack problem; Dynamic-programming; Branch-and-cut; Surrogate relaxation; Heuristics Abstract: Two heuristics for the 0-1 multidimensional knapsack problem (MKP) are presented. The first one uses surrogate relaxation, and the relaxed problem is solved via a modified dynamic-programming algorithm. The heuristics provides a feasible solution for (MKP). The second one combines a limited-branch-and-cut-procedure with the previous approach, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic-programming algorithm. Computational experiences show that our approaches give better results than the existing heuristics, and thus permit one to obtain a smaller gap between the solution provided and an optimal solution. Author Affiliation: LAAS-CNRS, Universite de Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France Article History: Received 9 September 2006; Accepted 8 June 2007
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users