Question 4 (6 + 3 + 5 = 14 marks) Consider the following pure IP: min 2 = s.t. 6x1 + 8x2 3x1 + x2 > 4 X1 + 2x2 > 4 x1, x2 > 0 and integer. The final/optimal Simplex tableau for its LP relaxation is shown as follows: basis 21 22 e2 rhs 4 18 2 0 0 88 5 4 C 21 1 0 22 0 1 5 where ei and e2 are the excess variables for the first and second constraints, respec- tively. (a) Solve the considered pure IP using the cutting-plane algorithm coupled with the dual Simplex method. Show all the step(s)/tableau(x) in detail. (No mark will be awarded if a correct cut constraint can not be generated.) (b) For the considered pure IP, any feasible solution requires that both xi and x2 be integers. Are the excess variables ej and e2 integers in any feasible solution to the considered pure IP? Please justify your conclusion. (No mark will be awarded if no correct reasoning is provided.) (c) In the cutting-plane algorithm procedure, a new slack variable is introduced for the cut constraint to generate a new equality constraint to be added to the LP-relaxation subproblem. Will the slack variable(s) introduced for the cut constraint(s) in (a) be integer(s) in any feasible solution to the considered pure IP? Please justify your conclusion. (No mark will be awarded if no correct reasoning is provided.)