Consider the binary ILP max 21x1 + 21x2 + 48x3 + 33x4 + 18x5

+ 17x6 + 39x7 s.t. 5x1 + 14x2 + 12x3 + 21x4 + 1x5

+ 6x6 + 13x7 … 30 [i]

x1 + x2 + x3 … 1 [ii]

xj binary for all j [iii]

(a) Use class optimization software to solve both the full ILP and its LP relaxation.

(b) Explain why minimum cover constraints 12.48 derived from constraints [i] and [iii]

are valid for the full model.

(c) Now consider solving the given ILP via Branch and Cut Algorithm l2B, starting from your LP relaxation of (a), and invoking class optimization software as each node is investigated. Use minimal cover inequalities from

(b) when adding appropriate cuts, and branch on the fractional variable with highest subscript. Branch after at most 3 cuts have been generated for any partial solution, and continue until a total of 5 nodes have been explored.