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
Comments and reviews
What are comments? Add a commentNo user comments or reviews for this work
Show comments and reviews from Amazon users