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

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.