Heuristics for the 0–1 multidimensional knapsack problem |
| |
Authors: | V. Boyer M. Elkihel D. El Baz |
| |
Affiliation: | aLAAS-CNRS, Université de Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France |
| |
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. |
| |
Keywords: | Multidimensional knapsack problem Dynamic-programming Branch-and-cut Surrogate relaxation Heuristics |
本文献已被 ScienceDirect 等数据库收录! |