ALGORITHM FOR 0-1 MULTIPLE-KNAPSACK PROBLEMS

被引：31

作者：

HUNG, MS ^{[1
]}

FISK, JC ^{[1
]}

机构：

[1] SUNY ALBANY,ALBANY,NY 12203

来源：

NAVAL RESEARCH LOGISTICS | 1978年 / 25卷 / 03期

关键词：

D O I：

10.1002/nav.3800250316

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The 0-1 multiple-knapsack problem is an extension of the well-known 0-1 knapsack problem. It is a problem of assigning m objects, each having a value and a weight, to n knapsacks in such a way that the total weight in each knapsack is less than its capacity limit and the total value in the knapsacks is maximized. A branch-and-bound algorithm for solving the problem is developed and tested. Branching rules that avoid the search of redundant partial solutions are used in the algorithm. Various bounding techniques including Lagrangean and surrogate relaxations, are investigated and compared.

引用

页码：571 / 579

页数：9