Question 5 (6 + 6 = 12 marks)

Consider the following pure IP:

max z = 3x1 + x2

s.t. 5x1 + x2 12

2x1 + x2 8

x1 0, x2 0; x1 integer, x2 integer.

The Simplex procedure for the LP relaxation of the considered IP ends with the

following final tableau:

basic x1 x2 s1 s2 rhs

z 0 0 1

3

2 3

28

3

x1 1 0 13 - 13 4 3

x2 0 1 - 2 3 53 16 3

where s1 and s2 are the slack variables for the first and second constraints, respectively.

(a) Solve the considered IP by the branch-and-bound algorithm coupled with the

Simplex method(s). Show the branching tree and all the step(s)/tableau(x) in

detail.

(b) Solve the given IP by the cutting-plane algorithm coupled with the Simplex

method(s), and show all the step(s)/tableau(x) in detail.