The following ILP problem has LP relaxation optimal solution x $=(0,0,0\mathrm{.}5238,0,0).$

min $4$x$1+5$x$2+12$x$3+7$x$4+6$x$5$

s$.$t$.6$x$1+8$x$2+21$x$3+6$x$4+5$x$5>=11$

x$1+$ x$2+2$x$3+$ x$4>=1$

$2$x$2+5$x$3+$ x$5>=2$

x$1,...,$ x$5=0$ or $1$

$($a$)(7$ pts$)$ Determine the best bound on the ILP optimal objective function value available from

relaxation results.

$($b$)(7$ pts$)$ Determine whether the LP relaxation optimum solves the ILP above. If not, round to a

feasible solution to the ILP either by moving all binary variables at fractional values in the LP

relaxation optimum up to $1$ or by moving all down to $0.$

$($c$)(6$pts$)$ Combine parts $($a$)$ and $($b$)$ to determine the best upper and lower bounds on the ILP

optimal objective function value