Consider the ILP min 10x1 + 20x2 + 40x3 + 80x4 - 144y s.t. x1 + x2 + x3 + x4 Ú 4y x1,c, x4, y = 0 or 1

(a) Solve the full ILP model by inspection.

(b) Verify by inspection that its LP relaxation has optimal solution x  = 11, 1, 0, 02, y 

= 12

.

(c) Show that an equivalent ILP would result if the main constraint were replaced by xj Ú y j = 1,c, 4

(d) Verify that the revised formulation of part

(c) has a stronger LP relaxation than the original of part (b).