The ILP max 40x1 + 5x2 + 60x3 + 8x4 s.t. 18x1 + 3x2 + 20x3 + 5x4 … 25 x1,c, x4 = 0 or 1 has LP relaxation optimum x  = 1 5 18, 0, 1, 02. Determine whether each of the following is a valid inequality for the ILP, and if so, whether it would strengthen the LP relaxation to add the inequality as a constraint.

(a) x1 + x3 … 1

(b) x1 + x2 + x3 + x4 … 3

(c) x2 + x4 Ú 1

(d) 18x1 + 20x3 … 25