The critical‐item, upper bounds, and a branch‐and‐bound algorithm for the tree knapsack problem

Journal Article


The tree knapsack problem (TKP) is a generalized 0–1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be packed. In this paper, we first define the so‐called critical‐item for the TKP and present an algorithm to find it. Then, we develop several upper bounds for the TKP. Finally, we present a branch‐and‐bound procedure for solving the TKP. Our computational results might suggest that our code is currently the most efficient procedure available in the literature. © 1998 John Wiley & Sons, Inc. Networks 31: 205–216, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.