A branch‐and‐bound algorithm for hard multiple knapsack problems

The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin‐completion, a bin‐oriented, branch‐and‐bound algorithm. In this paper, we propose path‐symmetry and path‐dominance criteria for pruning nodes in the MKP branch‐and‐bound search space. In addition, we integrate the ‘bound‐and‐bound’ upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound‐and‐bound, significantly outperforms previous solvers on some classes of hard problem instances.