QUESTION $4[25$ Marks$]$:

Solve the following knapsack problem by using the B&B algorithm $($when selecting the subproblem to be solved, choose always the branch that corresponds to the fractional variable imposed to be zero$).$ Start by defining in the first iteration both an UB and a LB$,$ then summarize your solution in the form of B&B tree that should include all the details.

max$24x_1+17x_2+12x_3+6x_4$

$10x_1+8x_2+6x_3+5x_{4}15$

$x_j=\{\begin{array}{c}1\\ j=1\\ 2\\ 3\\ 4\end{array}$

$0$

ANSWER: