Combinatorial optimization: Knapsack problem 1: Unterschied zwischen den Versionen

Version vom 27. Juni 2013, 17:37 Uhr

The Knapsack problem

1. Introduction

3. Methods

1. Introduction

The knapsack-problem is a problem in combinatorial optimization. The solution approach is to fill a certain object that has a given capacity limit, with items of different capacity and value. The optimal solution is the combination of items that sum up to the greatest value without crossing the capacity limit.

Originally the knapsack-problem is named after the following example: A backpacker needs to choose from a bunch of items to put in his rucksack but there is not enough space for all of them as he can only carry a specific amount of weight (e.g. 30 kg). These items all have a certain value to him and a given weight. The backpacker now has to pick the items with the biggest value while staying beneath the weight limit.

3. Methods

3.1. Kolesar

Max z = ∑ cjxj

∑ajxj ≤ b

xj = 0 oder 1

cj = value of object j

aj = capacity needed for object j

b = capacity

At first the quotient of cj and aj has to be built so that the resulting number shows the value of a specific item per weight unit. In this example our given capacity is b=80.

Afterwards the items are then sorted in descending order (based on value per weight unit).

Starting at the top, all variables are given the factor xj = 1 until one reaches a variable that crosses the capacity limit. In this example the item x1 is used once and weighs 36 units. Further the item x2 with a weight of 32 units is also used once. Now 68 of the allowed 80 weight units have been used up, so that it is not possible to add item x3 without crossing the limit. The remaining 12 weight units would allow us to take 0,6 units of the item x3. Items x4 and x5 are not used at all. The variable z indicates the cumulated value of all the items used for this solution:

Z = 1 * 6 + 1 * 4,8 + 0,6 * 2,8 = 12,48

The next step is to set variable x1=1, which would be the same solution as before (upper branch), and set x1=0 (lower branch). Now that x1=0, there is more capacity left for the other items. However the cumulated value z is not bigger than the first solution, so that this branch won’t be continued. The upper branch is continued by setting x2=0 on the one hand and x2=1 on the other. By setting x2=0, an integer solution has been found, which means an optimum could exist here. This scheme is continued until the last item, in this example x5, is reached. The optimum is the integer solution with the highest cumulated value z.

3.2. Greenberg & Hegerich

The Greenberg & Hegerich method is very similar to the Kolesar method. The tables used above are also the ones that are best suited here. The main difference between the two methods is that one doesn’t change the variables starting at the top. Instead the non-integer variable is changed. In the first step, this would apply to x3. As before, one sets the variable either to x3=1 or to x3=0. By setting x3=1, there is no longer enough capacity to keep both x1 and x2 (these are the two variables that have the highest cj/aj ratio). So x2 is reduced to the amount that fills the capacity completely. As both cumulated values are the same, one has to continue working with both branches. Starting at the top branch, the non integer variable x2 now has to be changed and set to x2=1 and x2=0. The same has to be done using x4 in the bottom branch. This then is continued until an optimal solution is found and all of the following cumulated values are smaller than the value found for the optimal solution.

3.3. Cascading Tree