An algorithm for 0‐1 multiple‐knapsack problems

Abstract

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.