The Unbounded Knapsack Problem
This paper presents a survey of the unbounded knapsack problem. We focus on the techniques for obtaining the optimal solutions, particularly those using the periodic structure of the optimal solutions when the knapsack weight-carrying capacity b is suffic
- PDF / 406,299 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 252 Views
Summary. This paper presents a survey of the unbounded knapsack problem. We focus on the techniques for obtaining the optimal solutions, particularly those using the periodic structure of the optimal solutions when the knapsack weight-carrying capacity b is sufficiently large. In addition to reviewing existing algorithms on the subject, the paper also includes two new algorithms, one for finding the onset of the optimal periodic solutions in time O(nw1 ), where w1 is the weight of the best item, i.e. the item with the highest value-to-weight ratio, and a second one for finding the optimal solutions when the capacity b is below the critical value where the optimal periodic solution begins. The second algorithm has a worst-case time complexity of O(nw1 v1 ), where v1 is the value of the best item.
10.1 Introduction The unbounded knapsack problem (UKP) arises from the following hypothetical situation. Consider a hiker with a knapsack on a trip. He has to select items to fill the knapsack. Every ith type item has a value vi and a weight wi , and the knapsack has a weight-carry capacity b. Mathematically, the problem is defined as follows: max V = subject to
n
v i xi i=1 n
(1)
wi x i ≤ b
i=1
with vi , wi , b, xi all non-negative integers. The Knapsack problem is the simplest integer programming problem with a single constraint, and belongs to the class of NP-complete problems (Garey and Johnson 1979). The topic started with a sequence of papers by Gilmore and Gomory (1966). Since then, two books (Kellerer et al. 2004, Martello and Toth 1990a) and over three hundred technical papers have been devoted to the knapsack problems in the last forty years.
202
T.C. Hu et al.
10.2 General Techniques for Finding Optimal Solutions 10.2.1 The Branch-and-Bound Solutions The most straightforward way for solving the UKP is to use the branch and bound technique which has a worst-case time complexity of O(2n ). The branch and bound algorithm can be speeded by successively pruning the search tree with revised lower and upper bounds. Any feasible solution gives a lower bound on the optimal value, and we can use linear programming relaxation to get an upper bound. Other concepts from duality can also be used. The class of algorithms based on branch and bound can be further speeded up when dominance relation exists between the item types. Assuming that the ith and the kth items have values and weights satisfying the relation vi > vk
and wi < wk
(2)
then the kth item is never used in any optimal solution. We say that the ith item dominates the kth item. We can use relation (2) to reduce the input size of the knapsack problem. The simple dominance relation (2) has been extended by several researchers into more generalized dominance relations (e.g. the multiple dominance by Martello and Toth (1990b) and the threshold dominance by Andonov et al. (2000)). See (Kellerer et al. 2004) for details. 10.2.2 The Dynamic Programming Solutions Due to the integer constraint on xi , the first optimal knapsack algorithm based on dynamic pr
Data Loading...
