EX$8.$ Suppose that a maximizing branch and bound search over $y_1,$dots,$y_4=\{0,1\}$ reaches partial

solution $y=($#$,0,$#$,$#$)$ with incumbent value of hat$(z)=100.$ Explain how the seacrh should proceed

assuming each of the following outcomes from an attempt to solve the linear programming

relaxation of the corresponding candidate problem:

a$)$ Relaxation optimum $y^{LP}=(\frac{1}{3},0,1,0)$ with an objective value of $z^{LP}=85.$

b$)$ Relaxation optimum $y^{LP}=(1,0,\frac{1}{2},0)$ with an objective value of $z^{LP}=100.$

c$)$ Relaxation optimum $y^{LP}=(0,0,1,1)$ with an objective value of $z^{LP}=120.$

d$)$ Relaxation infeasible.

e$)$ Relaxation optimum $y^{LP}=(0,\frac{1}{4},1,0)$ with an objective value of $z^{LP}=111.$