Problem 2: (Valid Inequalities and Cutting Planes) [20 points] For the following maximization problem: maxx14x2s.t.x1+2x24x1+x2x1,5.722.5x24.5x20,integer (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): apply the Gomori cutting plane algorithm on variable x1 (one iteration) and expand the tableau (one extra line and one column). (e) (4 points) Express the new cut only in terms of x1 and x2 variables. Hint: Convert the new tablenu into the form with one slack variable per constraint