Problem 2: (Valid Inequalities and Cutting Planes) [20 points] For the following maximization problem: max -x...

Transcribed Image Text:

Problem 2: (Valid Inequalities and Cutting Planes) [20 points] For the following maximization problem: max -x + S.L. -X1 + + XI. Basic 2 Z 1 XI X2 $2 4x2 1.99x26.5 X22 25.5 X2S 5.5 X₂20, integer 0 0 X1 X2 0.00 0.00 1.00 0.00 0.00 1.00 0 0.00 0.00 X2 (a) (4 points) Write down all constraints forming the convex hull (b) (4 points) Write down the convex hull definition as linear combination of all vertices. (c) (4 points) Generate a cut using the Chvatal-Gomori procedure. (d) (4 points) Given the final simplex tableau of the relaxed LP (for the problem above): Solution 17.55 4.55 5.50 2.22 6 5 2 1 0 0 1 2 3 4 5 6 7 X1 S1 32 53 1.00 0.00 2.01 1.00 0.00 1.99 0.00 0.00 1.00 4.00 1.00 -8.96 apply the Gomori cutting plane algorithm on variable x₂ (one iteration) and expand the tableau (one extra line and one column). (e) (4 points) Express the new cut only in terms of x₁ and .x2₂ variables. Hint: Convert the new tableau into the form with one slack variable per constraint Problem 2: (Valid Inequalities and Cutting Planes) [20 points] For the following maximization problem: max -x + S.L. -X1 + + XI. Basic 2 Z 1 XI X2 $2 4x2 1.99x26.5 X22 25.5 X2S 5.5 X₂20, integer 0 0 X1 X2 0.00 0.00 1.00 0.00 0.00 1.00 0 0.00 0.00 X2 (a) (4 points) Write down all constraints forming the convex hull (b) (4 points) Write down the convex hull definition as linear combination of all vertices. (c) (4 points) Generate a cut using the Chvatal-Gomori procedure. (d) (4 points) Given the final simplex tableau of the relaxed LP (for the problem above): Solution 17.55 4.55 5.50 2.22 6 5 2 1 0 0 1 2 3 4 5 6 7 X1 S1 32 53 1.00 0.00 2.01 1.00 0.00 1.99 0.00 0.00 1.00 4.00 1.00 -8.96 apply the Gomori cutting plane algorithm on variable x₂ (one iteration) and expand the tableau (one extra line and one column). (e) (4 points) Express the new cut only in terms of x₁ and .x2₂ variables. Hint: Convert the new tableau into the form with one slack variable per constraint

Answer rating: 100% (QA)

This problem set is related to linear programming and cutting plane methods used to solve integer linear programming problems I can guide you through the steps requested in the questions based on the ... View the full answer