Q$2$: Remember the integer knapsack problem that we saw in class last week:

$z^{IP}=$max$1x_1+5x_2+4x_3+5x_4$

$s.t.4x_1+10x_2+5x_3+4x_{4}29$

$3x_{1}0,2x_{2}0,1x_{3}0,2x_{4}0$ and integer

You will solve this problem using branch$-$and$-$bound solving the LPs using the greedy algorithm. You can stop after $5$ iterations $($i$.$e after solving $5$ LPs$).$ Show all your work.

$($a$)$ Show the resulting branch$-$and$-$bound tree.

$1$

$($b$)$ Do you have the optimal solution when you stop?

$($c$)$ If not, what is the UB and LB$.$