An algorithm for 0‐1 multiple‐knapsack problems

Ming S. Hung, John C. Fisk · Naval Research Logistics Quarterly · 1978

Abstract 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.

Cited by 69 works. doi:10.1002/nav.3800250316

Authors

References