Combinatorial optimization: Knapsack problem 3
Inhaltsverzeichnis
Theory
Given an amount of objects (xj) and every object having a certain value (cj) and using a certain capacity (aj), the combinatorial optimization determines the subset of these elements with that maximize the sum of the items value under integer consideration of the variables for a given capacity limit.
In formal terms this leads to:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \max z=\sum c_{j}x_{j}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum x_{j}a_{j}\leq b
xj = 0 or 1
cj = value of object j
aj = needed capacity of object j
b = existing capacity
The original problem was described in the process of packing a backpack (knapsack). The backpack has a certain capacity (e.g. 60 pounds) and one has to choose which things he wants to pack into the bag as all the things won´t fit in. As every item has a certain value and is using a certain capacity, one has to find the combination of items that maximizes the item´s value sum without exceeding the capacity limit of the backpack. The solution has to be integer as an item either fits in into the backpack without exceeding the capacity limit, or it does not fit in because it exceeds the capacity limit of the backpack.
Example
A student is facing the time in which s/he has to prepare and take exams. S/He has examined that in order to prepare properly (i.e. to pass the exam) s/he has a total time capacity of 100 preparation hours. As the student is already in 10th semester of her/his Bachelor s/he decided that s/he wants to gain as many credits as possible in the upcoming exam time. The student has some options concerning how many and which exams to write. S/He examined that s/he has a total number of 7 exams out of which s/he can choose in order to maximize the amount of credits gained in the upcoming exam period. Different exams need different preparation times and are weighted with different amounts of credits. The student also decided that the preparation time for a particular exam is either fulfilled completely or the exam is not taken at all. The ambitious student now is wondering which exams s/he should take in order to maximize the amount of credits that s/he can gain in this exam period without violating the total preparation hour’s capacity.
Can you help the student?
Solution
The definition of the example in formal terms is as follows:
z = credits gained in the upcoming exam period
cj = credits of the exam j
aj = needed preparation hours of exam j
b = total preparation hours capacity (100 preparation hours)
xj = the j exam
xj = 0 or 1 determines an integer solution, i.e. an exam is either taken because preparation hours can be fulfilled fully (xj =1), or an exam won´t be taken because the preparation hours aren´t fulfilled fully (xj = 0)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \max z=\sum c_{j}x_{j}
maximize the credits gained in the upcoming exam period by summing up the credits of all taken exams.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum x_{j}a_{j}\leq b
if an exam xj is taken, the sum of preparation hours of all taken exams must not exceed the preparation hours capacity limit
Generating the initial solution
The first step is to calculate the ratio of credits/preparation hours (cj/aj) in order to generate an order of the elements. Here, the elements are ranked descending concerning the ratio value i.e. starting with the highest credits per preparation hour ration, then the second highest and so on.
After reordering the elements one gets the following table:
One can now start by filling up the elements starting with the highest ranked item (x1 has 1.92 credits per preparation hour) and assigning it to 1. Then continue with the second highest element (x2 has 1,14 credits per preparation hour) until the capacity limit of 100 preparation hours is reached. In the example, the student takes x1,= x2 = x3 = x4 = 1 and thereby achieves z = 1*25 + 1*25 + 1*30 + 1* 18 = 98 credits. As the student has a total capacity of 100 preparation hours and with the 4 exams only uses 82 of them, s/he has still 18 hours left. Those 18 are assigned to the next variable after x5. However, x5 demands a preparation of 26h and therefore the remaining 18 hours are not enough and are written down as the non integer number 18/26, which, multiplied with the credits of x5 would generate additional credits of 15,23 to a total z = 1*25 + 1*25 + 1*30 + 1*18 + 18/26* 22 =113,23. As exams can only be passed if the full preparation time is given and used, the combinatorial optimization starts.
Methods
(1) Kolesar
The combinatorial optimization of Kolesar begins by branching the first variable to either 1 or 0. Setting x1=1 gives us the same solution as before. By setting x1=0, one gains capacity which one can allocate in a new way to the remaining elements. For x1=0 one gains 13 additional hours of preparation. Those are assigned to the non-integer variable (x5) which now can use 8 of the 13 hours to add them to the previous non-integer number 18/26 and make this variable 1. The remaining 13-8 = 5 hours then are assigned to the next variable x6. As x6 requires a total of 30 preparation hours and one only has 5 hours of capacity left, x6 gets the non-integer number of 5/30. At this point, z = 0*25 + 1*25 + 1*30 + 1*18 + 1*22 + 5/30*20= 98,33. One continues now by following the branch, which has a higher z value (x1=1), and branching it with the next variable (x2 = 1 or 0) and so on. As this is an optimization problem, the method stops as soon as the highest, integer solution is found.
(2) Greenberg & Hegerich
This method differs from Kolesar in that it does not start with x1 but rather with the non-integer variable and branches from there. In the example this means, that one starts with x5 and branches from that point with x5= 1 or 0. By setting x5 = 1, the capacity limit is exceeded and therefore one has to reduce x4 to 12/20. By setting x5 = 0, one gains 18 hours of preparation hours that can be allocated to the next variable x6. Again, as x6 requires 30 hours of preparation and one only has 18, this leads to the non-integer number of 18/30. Calculating z for x5 = 1 (z=112,8) and for x5 = 0 (z=110), one continues branching the branch with the higher z value (x5 =1). Again, the method stops as soon as the highest, integer solution is found.
(3) Heiner-Müller-Mehrbach – Cascading Tree
Again, the general idea is same as the two previous methods but differs in that the cascading tree focuses on multiple rather than single variables in the branching structure simultaneously. Also, the tables re divided into two columns. The left one indicates the non-integer solution whereas the right one shows the next possible integer solution. Further, the right side shows how to branch multiple variables simultaneously as all remaining variable with a 1 are changed towards a 0 and vice versa. Thereby the method warrants disjunctive branches.
Sources
Sources
1) https://bisor.wiwi.uni-kl.de/orwiki/Knapsack-Problem
2) https://en.wikipedia.org/wiki/Knapsack_problem
3) Müller-Mehrbach, Operations Research 3. Auflage, München 1973
