¹Hanyang University, South Korea

Correspondence: Y-J Seong, Department of Industrial Engineering, Hanyang University, 1271 Sa-1 dong, Sangnok-gu, Ansan, Kyunggi-do 425-791, South Korea. E-mail: ydudwh@empal.com

Received January 2002; Accepted November 2003.

Abstract

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 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 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.