Combinatorial optimization: Knapsack problem 1
Inhaltsverzeichnis
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.
Definition
Max z = ∑ cjxj
∑ajxj ≤ b
xj = 0 oder 1
cj = value of object j
aj = capacity needed for object j
b = capacity
Methods
Kolesar
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.
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.
Cascading Tree
The tables used in the cascading tree method are split up into two columns. One the left hand side the normal solution (till the capacity limit is reached) and on the right hand side the integer solution (variables filled up to the next integer solution).
To decide which variables will be changed one takes a look at the right side. Every 1 is changed to 0 and every 0 to 1. With this method there will be an integer solution on the right hand side in every step. So it is easy to see which one is the optimal solution.
Sources
Operations Research : Methoden und Modelle der Optimalplanung. Vahlen, München 1973
