An improved branch and bound algorithm for a strongly correlated unbounded knapsack problem

Abstract

An unbounded knapsack problem (KP) was investigated that describes the loading of items into a knapsack with a finite capacity, An unbounded knapsack problem (KP) was investigated that describes the loading of items into a knapsack with a finite capacity, W so as to maximize the total value of the loaded items. There were so as to maximize the total value of the loaded items. There were n types of an infinite number of items, each type with a distinct weight and value. Exact branch and bound algorithms have been successfully applied previously to the unbounded KP, even when types of an infinite number of items, each type with a distinct weight and value. Exact branch and bound algorithms have been successfully applied previously to the unbounded KP, even when n and W were very large; however, the algorithms are not adequate when the weight and the value of the items are strongly correlated. An improved branching strategy is proposed that is less sensitive to such a correlation; it can therefore be used for both strongly correlated and uncorrelated problems.