An algorithm for 0‐1 multiple‐knapsack problems

Ming S. Hung and John C. Fisk

Naval Research Logistics Quarterly, 1978, vol. 25, issue 3, 571-579

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.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/nav.3800250316

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:25:y:1978:i:3:p:571-579

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().