The integer linear program (ILP) max 40x15x2 + 60x3 +8x4 s.t. 18x13x2 +20x3+5x4 25 X1, X2,...

   

Transcribed Image Text:

The integer linear program (ILP) max 40x15x2 + 60x3 +8x4 s.t. 18x13x2 +20x3+5x4 25 X1, X2, X3, X4 {0,1} has linear programming (LP) relaxation optimum x = 5 18, X2 = (1) (2) (3) 0, x3 = 1, and x4 = 0. 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 4 (c) x2 + x4 1 (d) 18x120x3 20 (e) Based on your answers to parts (a), (b), (c), and (d), find the tightest bounds you can on the optimal ILP objective function value. The integer linear program (ILP) max 40x15x2 + 60x3 +8x4 s.t. 18x13x2 +20x3+5x4 25 X1, X2, X3, X4 {0,1} has linear programming (LP) relaxation optimum x = 5 18, X2 = (1) (2) (3) 0, x3 = 1, and x4 = 0. 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 4 (c) x2 + x4 1 (d) 18x120x3 20 (e) Based on your answers to parts (a), (b), (c), and (d), find the tightest bounds you can on the optimal ILP objective function value.