An extension of Dembo-Hammer’s reduction algorithm for the 0-1 knapsack problem

Yang Yang · 2025

Read An extension of Dembo-Hammer’s reduction algorithm for the 0-1 knapsack problem by Yang Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06138.txt.

Introduction

Yang Yang extends a classic shortcut for the knapsack problem in a 2025 solo paper. The 0-1 knapsack problem asks which items to pack for most value. Dembo and Hammer gave a fast reduction that shrinks each case. Their method cuts a case to a smaller sub-case in linear time.

Yang's extension can split a case into many sub-cases at once. The user picks how wide that split may grow. At the narrowest setting it matches the classic method exactly. Tests on random data show much smaller search trees. The rival here was CPLEX, a top commercial solver. The gains suggest real speed value for hard packing tasks.

Catalog record

CREATORYang Yang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06138

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An extension of Dembo-Hammer’s reduction algorithm for the 0-1 knapsack problem Yang Yang Abstract 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 ) O(n) . We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1 KP to at most n i n^{i} sub-instances for any positive integer i i . In practice, i i can be set as needed. In particular, if we choose i = 1 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. keywords 0-1 knapsack problem(0-1 KP), exact solution, time complexity, polynomial-time, reduction, CPLEX 1 Introduction Given an item set N=\{1,2,\cdots,n\} , let p_{j} and w_{j} denote the profit and weight of the j -th item, respectively. In classical 0-1 Knapsack Problem (0-1 KP), the goal is to select a subset of items from the set N such that the sum of their weights does not exceed a given capacity C . The objective is to maximize the total profits of the chosen items Kellerer2004 ; Pisinger1997 ; Balas1980 ; Bellman1957 ; Martello1999 ; Martello2000 . In terms of (0,1) -vector, the 0-1 KP can be formulated as the following programming: Definition 1 . (0-1 KP). \displaystyle\max f(\bm{X})=\sum\limits_{j=1}^{n}x_{j}p_{j} (1) subject to \displaystyle g(\bm{X})=\sum\limits_{j=1}^{n}x_{j}w_{j}\leq C (2) \displaystyle\hskip 35.0ptx_{j}\in\{0,1\} (3) For j\in N , x_{j}=1 indicates that the j -th item is packed in the knapsack while x_{j}=0 indicates not. For simplicity, we assume that p_{j} , w_{j} and C are positive integers for any j\in N Kellerer2004 . Meanwhile, in order to avoid trivial solution, we assume w_{j}<C for any j\in N and \sum_{j=1}^{n}w_{j}>C . In the algorithms of the 0-1 KP typically employed, one of the key points for solving the 0-1 KP is initially to order the variables according to non-increasing profit-to-weight e_{j}=p_{j}/w_{j} ratios, also called the profit density . Therefore, we also assume the following e_{1}\geq e_{2}\geq\cdots\geq e_{n}. The 0-1 KP is known as NP-hard problem Garey1979 ; Karp1972 . Except the Dynamic Programming Bellman1957 that can exactly solve the 0-1 KP in pseudo-polynomial time, there is currently no polynomial time complexity algorithm that can exactly solve the 0-1 KP. Therefore, various methods or strategies for fast dimensionality reduction of problems in polynomial time have received much attention, that is, to reduce the size of an instance of the 0-1 KP through a reduction algorithm with polynomial complexity that partitions the item set N into three subsets N_{0},N_{1} and F so that the items in N_{1} are all included in any optimal solution while every item in N_{0} is not. Thus the optimal solution of the instance is given by N_{1}+N_{F} , where N_{F} is an optimal solution of the sub-instance of the original one restricted on F , that is, an instance of size |F| . Along this direction, a number of reduction algorithms were proposed. For examples, we refer to the Ingargiola and Korsh’s Reduction algorithm (IKR) Ingargiola1973 with time complexity of O(n^{2}) by Dantzig bound Dantzig1957 ; Martello and Toth’s Reduction algorithm(MTR) with time complexity to O(n\log n) by Reduction with Complete Sorting(RCS) and Reduction with Partial Sorting(RPS) Martello1988 . Further, based on MTR, in 1990 Martello and Toth proposed MTR2 Martello1990 to get a better solution. In addition, Dembo and Hammer proposed a Reduction algorithm (DHR) Dembo1980 , which reduces an instance of the 0-1 KP with n items to be a sub-instance of |F|=n-\left|\left\{j<b:\frac{p_{j}}{w_{j}+r}>\frac{p_{b}}{w_{b}}\right\}\right|-\left|\left\{j\geq b:\frac{p_{j}}{w_{j}-r}<\frac{p_{b}}{w_{b}}\right\}\right| items with reduction time complexity O(n) , where r is the residual capacity, i.e., r=C-\sum_{k=1}^{b-1}w_{k} , and b is the break item( also called the split\ item in literature Pisinger2005 ), i.e. b=\min\{k:\sum_{j=1}^{k}w_{j}>C\} . DHR has received widespread attention because of its simplicity and effectiveness, and its ease of hybridizing with other algorithms. Although DHR alone is not as efficient as IKR, MTR and MTR2 Martello1988 ; Fahle2002 , Pisinger in 1995 presented EXPKNAP Pisinger1995a based on the core strategy Balas1980 , which has better performance than MTR and MTR2. Later in 1997, MINKNAP Pisinger1997 was proposed based on EXPKNAP and DHR, the performance of which is better than EXPKNAP. In addition to being used to solve the 0-1 KP, DHR also has more applications for some extended models of the knapsack problem. Tsesmetzis et al. Tsesmetzis2008a transformed QoS-aware problem to Selective Multiple Choice Knapsack Problem and designed an algorithm with time complexity between O(n\log n) and O(n^{2}) through DHR as lower bound, which increases the provider’s profit up to 0.5% on average. Egeblad and Pisinger solved the two- and three-dimensional knapsack packing problem with semi-normalized packing algorithm and DHR Pisinger2009a . Using DHR, Pisinger and Saidi also analysed the tolerance of 0-1 KP Pisinger2016a . Recently, Dey et al. Dey2023 proposed a method to analyse the upper bound of the nodes in search tree of the Branch and Bound algorithm, and prove that the branch and bound algorithm can solve random binary integer programming in polynomial time. In this paper, we propose an extension of Dembo-Hammer’s Reduction Algorithm (EDHR). For any positive integer i , the algorithm EDHR reduces an instance of KP with n items to be n^{i} sub-KP sub-instances of |F|=n-\left|\left\{j<b:\frac{p_{j}}{w_{j}+r/i}>\frac{p_{b}}{w_{b}}\right\}\right|-\left|\left\{j\geq b:\frac{p_{j}}{w_{j}-r/i}<\frac{p_{b}}{w_{b}}\right\}\right|. items with reduction time complexity O(n) . In practice, i can be set by need. In particular, if we choose i=1 then EDHR is exactly DHR. Finally, we perform the computational experiment for some data instances that are constructed randomly. Our experiment shows that, compared with CPLEX, EDHR significantly decreases the search tree size for the instances. Our method also reduces the interval gap of the distances from power of 2 to integer and decreases the complexity of the method given by Dey et al. 2 Dembo and Hammer’s Reduction Algorithm If we relax the integrality constraint x_{j}\in\{0,1\} to the linear constraint 0\leq x_{j}\leq 1 , we obtain the Linear Knapsack Problem (LKP) Pisinger1997 . Let \bm{X}^{*}=(x^{*}_{1},x^{*}_{2},\ldots,x^{*}_{n}) be an optimal solution to LKP, where 0\leq x^{*}_{j}\leq 1 for each j\in\{1,2,\ldots,n\} . It is clear that x_{j}^{*}=1 if j<b , x_{j}^{*}=0 if j>b and x^{*}_{b}=(C-\sum_{i=1}^{b-1}w_{i})/w_{b} . This yields naturally an upper bound, called Dantzig bound, for the 0-1 KP Dantzig1957 : \displaystyle U=\sum\limits_{k=1}^{b-1}p_{k}+\left\lfloor rp_{b}/w_{b}\right\rfloor, where \lfloor x\rfloor is the greatest integer no more than x and r=C-\sum\limits_{k=1}^{b-1}w_{k} , called the the residual capacity . On the other hand, the integer solution \bm{X}^{\prime}=(x^{*}_{1},\ldots,x^{*}_{b-1},0,\ldots,0) is a solution to KP, which is known as the break solution . This yields naturally a lower bound of the 0-1 KP Pisinger1997 ; Pisinger1995a , i.e., \displaystyle L=\sum\limits_{k=1}^{b-1}p_{k}. Let \bm{X}=(x_{1},x_{2},\ldots,x_{n}) be an arbitrary solution of KP. Note that the upper bound U and lower bound L do not mean that x_{j}=1 for every j=1,2,\ldots,b-1 and x_{j}=0 for j=b,\ldots,n . Moreover, the items where x_{j}\not=x^{\prime}_{j} are generally very close to the break item b . Pisinger attempted to test this conclusion by constructing 1000 data instances with n=1000 , where p_{j} and w_{j} were randomly distributed within the interval [1,1000] . The capacity C was chosen such that the break item

Read the complete text