A branch-and-bound algorithm for hard multiple knapsack problems
A branch-and-bound algorithm for hard multiple knapsack problems
复制标题
DOI：
10.1007/s10479-009-0660-y
复制
发表时间：
2011-04
影响因子：
4.8
通讯作者：
A. Fukunaga
中科院分区：
文献类型：
--
作者：
A. Fukunaga
多背包问题（MKP）是一个经典的组合优化问题。最近的一些类的MKP算法是箱完成，面向箱，分支定界算法。在本文中，我们提出了路径对称和路径优势的标准修剪节点的MKP分支定界搜索空间。此外，我们集成了“有界和有界”的上限验证技术在以前的MKP求解器。我们的实验表明，我们的新的MKP求解器，成功地集成了基于优势的修剪，对称性破坏，并绑定和绑定，显着优于以前的求解器在某些类的硬问题的实例。
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.