Combinatorial optimization: Knapsack problem 2

The Knapsack-problem is an optimization problem, where a quantity of objects with corresponding weights and benefits is given. The aim is to choose a subset of these objects such that the total weight doesn't exceed a given threshold and the total benefit is maximal. This Problem is also called "backpack-problem" since it results from an example in which a hiker has to pack his backpack. He has to answer the question: how can I fill the 50 liter space of the backpack to get an optimal benefit.

Definition and formulation

An instance of the Knapsack-problem consists of an index-set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): I = \{ 1, \ldots, k \}

of $k$ objects, weights Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_i \in \mathbb{R}
and benefits Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_i \in \mathbb{R}
for each object Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \in I
and a maximum weight Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b \in \mathbb{R}

. An optimal solution of that instance is an subset Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): I' \subseteq I

with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i \in I'} a_i \leq b
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i \in I'} c_i
maximal.

The problem can be formulated as a Binary Linear Program as follows:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{alignat}{3} \max & \sum_{i \in I} x_i \cdot c_i & \\ \mathrm{s.t.} & \sum_{i \in I} x_i \cdot a_i \leq b &\\ & x_i \in \{ 0, 1\} & \forall i \in I \end{alignat}

Replacing the binary conditions Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_i \in \{0,1\}

with the weaker conditions Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  0 \leq x_i \leq 1 

, one gets the "relaxed" or "fractional knapsack problem".

Example

A woman wants to go on vacations. But she has to overcome a serious problem, because the airline prescribe a maximum weight of 25 kg ($b=25$) for her luggage (the worst that can happen to a woman). She has the choice between six different items $I=\{1,2,3,4,5,6\}$ which she can pack. Each object has a special benefit $c_{i}$ for the woman and a weight $a_{i}$. What items should be selected by her to have the maximum benefit without exceeding the maximum weight of 25 kg?

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Solution methods

For the knapsack problem, there are plenty of different solution methods. In this section, the most important solution methods are presented.

To be able to apply the first three of the presented methods a ranking must be made in advance.

For this purpose, a quotient is formed from the benefit $c_{i}$ and the weight $a_{i}$. Afterwards, the objects are sorted according to these values.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Ordered list:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

This list is the basis for the following three methods.

Kolesar

The goal is to obtain an integer solution. One begins with the object of rank 1, then rank 2 and so on and sets the variable equal 1 or 0. The items can be taken as long as the maximum weight of 25 kg is reached. This means that the last possible item mostly can't be taken completely. The solution with the highest objective function value is branched first. If the objective function value is less than the value that provides the best integer solution, this solution is not branched.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Note that the solution in the root node is an optimal solution to the fractional variant of the knapsack problem.

Greenberg & Hegerich

In this method, one starts with the non-integer variable and sets this variable equal 0 and 1 respectively to look for a better solution. This should be continued until an optimal solution is found. The procedure is similar to the first presented method.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Cascading Tree

In this method, every step consists of two columns. The left column is the normal solution(compares to the column in the other two methods). The right column is defined by setting the variable 0 which is not integer in the left solution. So the right one is called the integer solution. For the next step you set the variables 1 which are 0 in the integer solution. In the following steps you repeat this approach for getting the optimal solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Dynamic Programming

While the first three presented methods work in a Branch-and-Bound manner, a very popular method is based on Dynamic Programming. Here, a table is computed incrementally using already computed table entries, such that double computations are avoided. In the case of the knapsack problem, a cell in row $\lambda$ and column $i$ contains the maximal benefit one can get out of the first Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \leq k

entries at budget Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq \lambda \leq b

. Let $f_{i}(\lambda )$ represent this value.

Computing cell $(i,\lambda )$, there are two cases:

• Element Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \in I

isn't taken into the knapsack. Then the entry in cell $(i,\lambda )$ is equal to cell Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (i-1,\lambda)

, since the benefit doesn't change, so Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_i(\lambda) = f_{i-1}(\lambda) .

• Element Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \in I

is taken into the knapsack. Then the profit increases by $c_{i}$, while the weight of the knapsack increases by $a_{i}$. In other words, the optimal benefit is $c_{i}$ plus the optimal benefit of a knapsack with total weight Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda - a_i

. Therefore: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_i(\lambda) = c_i + f_{i-1}(\lambda - a_i)

in this case.

To achieve the optimal benefit, the best of these two cases is done, i.e.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_i(\lambda) = \max\{ f_{i-1}(\lambda), c_i + f_{i-1}(\lambda - a_i)\}.

Filling the table from top to bottom and from left to right, both cases can be evaluated by just looking up the corresponding table entries, which are already computed. Additionally, $f_{0}(\lambda )=0$ for all $\lambda$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_i(\lambda) = -\infty

for all negative $\lambda$.

It should be clear, that the optimal solution can afterwards be found in row $b$ and column $k$, since here every item and the correct budget is considered.

Using this recursion scheme, the following table can be computed for the given (unsorted) example:

$\lambda$	1	2	3	4	5	6
0	0	0	0	0	0	0
1	0	0	0	0	0	0
2	0	0	0	0	0	0
3	0	0	0	0	0	0
4	0	0	0	0	0	0
5	0	0	0	10	10	10
6	0	0	0	10	10	10
7	9	9	9	10	10	10
8	9	9	9	10	10	10
9	9	9	9	10	10	10
10	9	18	18	18	18	18
11	9	18	18	18	18	18
12	9	18	18	19	19	19
13	9	18	18	19	19	19
14	9	18	18	19	19	19
15	9	18	18	28	28	28
16	9	18	18	28	28	28
17	9	27	27	28	28	28
18	9	27	27	28	28	28
19	9	27	27	28	28	28
20	9	27	27	28	28	28
21	9	27	27	28	28	28
22	9	27	27	37	37	37
23	9	27	27	37	37	37
24	9	27	27	37	37	37
25	9	27	31	37	37	37

Looking at row 25 in column 6, one gets the optimal solution 37.

Complexity

The knapsack problem is known be ${\mathcal {NP}}$-complete, which means, that a polynomial time algorithm can't be found unless ${\mathcal {P}}={\mathcal {NP}}$. While the presented Branch-and-Bound methods have a exponential running time in the worst case, the Dynamic Programming scheme hat a running time of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \mathcal{O}(b \cdot k) . In fact, this performance is only pseudo-polynomial, since $b$ is given as a number and has a logarithmical encoding size. This shows, that the problem is only weak-${\mathcal {NP}}$-hard.

Contrary, the fractional variant can be found in polynomial time, as is was shown in the previous section.