Question: Solve the following knapsack problem using the branch and bound technique.

maxz$=5x_1+8x_2+3x_3+7x_4$

$s.t.$

$3x_1+5x_2+2x_3+4x_{4}6$

$x_1,x_2,x_3,x_{4}in\{0,1\}$

Instructions:

Draw the complete branch and bound tree $(aswe$ did $in$ class$).$

Fill $in$ the provided table below $to$ report solutions, objective function value, upper and lower bounds for

each node.

Write your optimal solution $in$ the following format:

$x^{*}=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=[],z^{*}=$

Please solve ASAP.