Combinatorial optimization: Knapsack problem 3
1. 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.
2. 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?
3. 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.
