Question $3(20$ points$)$ Consider a mixed integer program with three variables $1,2,3.1$ and $2$ are required to integer values. $3$ can take any value. The picture below shows the branch$-$and$-$bound tree in themiddle of solving this problem.

z$*=41\mathrm{.}25$ SP$1$

x$1=1\mathrm{.}167,$ x$2=0,$ x$3=5\mathrm{.}58$

SP$2$

SP$3$

z$*=42\mathrm{.}13$ z$*=42\mathrm{.}37$ x$1=1,$ x$2=0\mathrm{.}37,$ x$3=4\mathrm{.}55$

x$1=2,$ x$2=0\mathrm{.}43,$ x$3=3\mathrm{.}54$

SP$4$ SP$5$

SP$6$

SP$7$

z$*=43\mathrm{.}15$ z$*=44\mathrm{.}6$ z$*=43\mathrm{.}57$ x$1=0\mathrm{.}89,$ x$2=0,$ x$3=5\mathrm{.}98$

x$1=0\mathrm{.}65,$ x$2=1,$ x$3=4\mathrm{.}38$

INFEASIBLE

x$1=2\mathrm{.}1,$ x$2=0,$ x$3=3\mathrm{.}33$

SP$8$

z$*=44\mathrm{.}5$ z$*=45\mathrm{.}5$ x$1=0,$ x$2=0,$ x$3=7\mathrm{.}47$

SP$9$

x$1=1,$ x$2=0,$ x$3=5\mathrm{.}32$

$2$

$($a$)(15$ points$)$ For subproblems SP$5,$ SP$6,$ SP$7,$ SP$8$ and SP$9,$ indicate whether you need to

continue branching. If the answer is no$,$ briefly explain why not.

$($b$)(5$ points$)$ According to this branch$-$and$-$bound tree, what is the range $($lower and upper

bounds$)$ in which the optimal objective function value of the mixed integer program lies?

Explain your answer.

Question $4(20$ points$)$