[Math] 0/1 knapsack upper bound

algorithmsbinary-programmingdiscrete optimizationinteger programming

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as:

Knapsack max weight: 12

i     Weight     Profit     Profit/Weight
1      4           30          7.5
2      6           42           7
3      6           36           6
4      4           8            2

Calculating the upper bound:

Going off of the lecturers slides for a similiar example, the upper bound is then calculated by adding the items at the top of this list to the knapsack, this leaves us with only items 1 and 2 and a space left over with a total of 72 profit.

Clearly items number 2 and 3 also fit into the max weight and create a higher upper bound. Is there something I'm supposed to do to avoid this or do I continue with the process?

Best Answer

The IP is:

$$\max \Pi = 30x_1 + 42x_2 + 36x_3+ 8x_4$$ $$s.t.$$ $$4x_1 +6x_2 + 6x_3 +4x_4≤12$$ $$x_i \in \text{{$0,1$}}$$

What you did gives a lower bound of $72$ on the max. In order to find an upper bound, RELAX the integrality constraint of $x_i \in \text{{$0,1$}}\to x_i\in [0,1]$

Now, it is clear that we can use a greedy strategy for this:

solution: $x_1=1, x_2=1, x_3=\frac 13 \Rightarrow \Pi_{ub} = 84$

Thus, $72≤\Pi^*≤84$

Now, we use branch and bound...

Build a tree

Condition on the value of $x_3$, solve the program twice using our greedy strategy fixing $x_3=1$ and forcing $x_3=0$.

$x_3=1$

$\Rightarrow solution\text{ }x_3=1,x_1=1, x_2=\frac 13 \Rightarrow \Pi=80$

$x_3=0$

$\Rightarrow solution\text{ }x_3=0,x_1=1, x_2=1, x_4= \frac 12 \Rightarrow \Pi=76$

Now, pick a side of the tree to branch again on.

choose $x_3=1$ now, there are two possibilities $x_2=0, x_2=1$

Now, we fix $x_3=1, x_2=1 \Rightarrow \text{ solution }x_3=1, x_2=1 \Rightarrow \Pi = 78 = \Pi_{candidate}$ This is a candidate solution because it is integral

Now, we need to show that the previous solution is optimal.

choose $x_3=1, x_2=0 \Rightarrow \text{ solution }x_3=1, x_2=0, x_1=1, x_4=\frac 12 \Rightarrow \Pi = 70$ So, we can prune this branch of the tree since $70<\Pi_{candidate}$

Look at the other side of the tree with $x_3=0$ fixed

We have two possibilities: $x_4=0, x_4=1$

$x_3=0, x_4=0 \Rightarrow \text{ solution }x_1=1, x_2=1 \Rightarrow \Pi = 72 < \Pi_{candidate}$ again, we prune this branch since our candidate solution is better.

$x_3=0, x_4=1 \Rightarrow \text{ solution }x_1=1, x_2=\frac 23, x_4=1 \Rightarrow \Pi = 66 < \Pi_{candidate}$ again, we prune this branch since our candidate solution is better, and we're done since the tree has no more branches.

Hence, $\Pi^* = 78 \text{ with }x_1=0, x_2=1, x_3=1, x_4=0$

Related Question