A recursive branch and bound algorithm for the multidimensional knapsack problem
A recursive branch and bound algorithm for the multidimensional knapsack problem
复制标题
多维背包问题的递归分支定界算法
DOI：
--
复制
发表时间：
1975
期刊：
影响因子：
--
通讯作者：
A. Thesen
中科院分区：
文献类型：
--
作者：
A. Thesen
本文提出一种求解多约束背包问题的有效分支定界算法。该算法的关键是一个严格定义的树结构，其中分支和边界可以通过递归关系来执行。当只有有限数量的核心存储可用时，该算法特别有用，因为在任何一个时间仅保存当前和一个先前的解决方案。执行速度与其他算法相比毫不逊色。给出了数值算例和计算经验。
This paper presents an efficient branch and bound algorithm for the solution of certain multiconstrained knapsack problems. The key to this algorithm is a rigidly defined tree structure in which branching and bounding may be performed through recursive relationships. The algorithm is particularly useful when only limited amounts of core storage are available as only the current and one previous solution is saved at any one time. Execution speeds compare favorably with other algorithms. A numerical example and computational experience is given.