Exercise $8\mathrm{.}10$ Use the branch$-$and$-$bound method to solve the binary linear

programming model:

max,$8x_1+11x_2+6x_3+4x_4$

$s.t.6\mathrm{.}7x_1+10x_2+5\mathrm{.}5x_3+3\mathrm{.}4x_{4}19$

$,8x_1+2x_{2}19$

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

Compare the number of nodes in the branch$-$and$-$bound tree with the following

naive brute$-$force enumeration approach: check each of the $2^4=16$ possible

values of $x={\left[\begin{array}{cccc}{x}_1& x_2& x_3& x_4\end{array}\right]}^{TT}$ with $x_{i}in\{0,1\},$ for $i=1,$dots,$4,$ and pick the

best feasible solution among them.