






















Dembo-Hammer's Reduction Algorithm (DHR) is one of the classical algorithms for the 0-1 Knapsack Problem (0-1 KP) and its variants, which reduces an instance of the 0-1 KP to a sub-instance of smaller size with reduction time complexity $O(n)$. We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1 KP to at most $n^i$ sub-instances for any positive integer $i$. In practice, $i$ can be set as needed. In particular, if we choose $i=1$ then EDHR is exactly DHR. Finally, computational experiments on randomly generated data instances demonstrate that EDHR substantially reduces the search tree size compared to CPLEX.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。