Suppose that a maximizing Mixed Integer Linear Program is being solved by the Branch and Bound

algorithm over decision variables $x_{1}0$ and $x_2,x_3,x_4=0$ or $1.$ Assume that the incumbent solution

value is $85$ and show how the search should process the node with $x_4=0$ and other variables free if

the corresponding LP relaxation has each of the following outcomes.

Evaluate each part individually $($independent of the others$).$

a$.x^{LP}=(0\mathrm{.}2,0\mathrm{.}6,0\mathrm{.}8,0),$ value $z^{LP}=85$

b$.$ LP relaxation infeasible

c$.x^{LP}=(3\mathrm{.}3,0,1,0),$ value $z^{LP}=87$

d$.x^{LP}=(2\mathrm{.}1,0,0\mathrm{.}4,0),$ value $z^{LP}=89$