The ILP max 3x1 + 6x2 + 4x3 + 10x4 + 3x5 s.t. 2x1 + 4x2 + x3 + 3x4 + 7x5 … 10 x1 + x3 + x4 … 2 4x2 + 4x4 + 4x5 … 7 x1,c, x5 = 0 or 1 has LP relaxation optimal solution x  =

10, 0.75, 1, 1, 02.

(a) Determine the best bound on the ILP optimal solution value available from relaxation results.

(b) Determine whether the relaxation optimum solves the full ILP. If not, round to an ILP-feasible solution either by moving all binary variables at fractional values in the relaxation up to 1 or by moving all down to 0.

(c) Combine parts

(a) and

(b) to determine the best upper and lower bounds on the ILP optimal solution value available from the combination of relaxation and rounding.

(d) Verify your bounds of part

(c) by solving the full ILP with class optimization software.