NEW GREEDY-LIKE HEURISTICS FOR THE MULTIDIMENSIONAL 0-1 KNAPSACK-PROBLEM

被引：64

作者：

LOULOU, R

MICHAELIDES, E

机构：

来源：

OPERATIONS RESEARCH | 1979年 / 27卷 / 06期

关键词：

723 Computer Software; Data Handling and Applications;

D O I：

10.1287/opre.27.6.1101

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The authors develop four heuristic methods to obtain approximate solutions to the multidimensional 0-1 knapsack problem. The four methods are tested on a number of problems of various sizes. The solutions are compared to the rigorous optimum as well as to a heuristic method of Y. Toyoda. They are statistically better than the latter, with average relative errors of the order of less than 1%.

引用

页码：1101 / 1114

页数：14

共 11 条

[1]

FULKERSON DR, 1974, MATH PROGRAMMING STU, P72

[2]

INGIARGOLA G, 1975, OPER RES, V23, P1110

[3]

LORIE JH, 1955, J BUS, V6, P229

[4] WHEN GREEDY SOLUTION SOLVES A CLASS OF KNAPSACK PROBLEMS [J].

MAGAZINE, MJ ;

NEMHAUSER, GL ;

TROTTER, LE .

OPERATIONS RESEARCH, 1975, 23 (02) :207-217

[5]

McMillan C, 1973, DECISION SCI, V4, P119

[6]

Petersen C. C., 1967, MANAGE SCI, V13, P736

[7] KNAPSACK PROBLEM - SURVEY [J].

SALKIN, HM ;

KLUYVER, CAD .

NAVAL RESEARCH LOGISTICS, 1975, 22 (01) :127-144

[8] SIMPLIFIED ALGORITHM FOR OBTAINING APPROXIMATE SOLUTIONS TO ZERO-ONE PROGRAMMING PROBLEMS [J].

TOYODA, Y .

MANAGEMENT SCIENCE SERIES B-APPLICATION, 1975, 21 (12) :1417-1427

[9] METHODS FOR SOLUTION OF MULTIDIMENSIONAL 0/1 KNAPSACK PROBLEM [J].

WEINGARTNER, HM ;

NESS, DN .

OPERATIONS RESEARCH, 1967, 15 (01) :83-+

[10]

WEINGARTNER HM, 1967, MATH PROGRAMMING ANA

← 1 2 →