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
- Discrete-Variable Extremum Problems
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- Lagrangean relaxation for integer programming
- The Loading Problem
- Integer Programming Algorithms: A Framework and State-of-the-Art Survey
- An Improved Implicit Enumeration Approach for Integer Programming
- A branch and bound algorithm for the generalized assignment problem
- Discrete Programming by the Filter Method
- Surrogate Constraints
- The knapsack problem: A survey