Heuristics for the 0-1 multidimensional knapsack problem

被引：50

作者：

Boyer, V. ^{[1
]}

Elkihel, M. ^{[1
]}

El Baz, D. ^{[1
]}

机构：

[1] Univ Toulouse, CNRS, LAAS, F-31077 Toulouse 4, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2009年 / 199卷 / 03期

关键词：

Multidimensional knapsack problem; Dynamic-programming; Branch-and-cut; Surrogate relaxation; Heuristics; ALGORITHMS;

D O I：

10.1016/j.ejor.2007.06.068

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：658 / 664

页数：7

共 19 条

[1]

Beasley J.E., 2003, OR LIB

[2] An approximate dynamic programming approach to multidimensional knapsack problems [J].