4. (15 points) The final simplex table for the LP relaxation of an IP is given...

 

Transcribed Image Text:

4. (15 points) The final simplex table for the LP relaxation of an IP is given below, where s and 82 are the slack variables corresponding to the first and second con- straints of the original model. Generate all valid cuts that can be obtained from this table. Do not solve. Show the derivations explicitly. x1 x2 X3 S S2 RHS 0 0 6 2 0 148 1 0 0 100 1.6 -0.2 0 6.4 -3.2 0.4 1 2.2 1 0 0 4 4. (15 points) The final simplex table for the LP relaxation of an IP is given below, where s and 82 are the slack variables corresponding to the first and second con- straints of the original model. Generate all valid cuts that can be obtained from this table. Do not solve. Show the derivations explicitly. x1 x2 X3 S S2 RHS 0 0 6 2 0 148 1 0 0 100 1.6 -0.2 0 6.4 -3.2 0.4 1 2.2 1 0 0 4