The following graph G = (V,E) is used in questions 1 and 2.

1. Consider a node packing problem on the above graph, with each vertex having weight 1. The LP relaxation includes the clique constraints ∑ _vCx_v ≤ 1 for each maximal clique C in the graph. The point x_A = 0.4, x_B = 0.6, x_C = 0.4, x_D = 0.5, x_E = 0.4, x_F = 0.5, x_G = 0.1, x_H = 0.4, and x_J = 0.1 is feasible in the LP relaxation.
   1. Show that the given point is not in the convex hull of feasible solutions, by giving a valid constraint that is violated by this point.
   2. Find an optimal solution to the node packing problem for this graph. Prove your solution is optimal.
2. Consider a matching problem on the graph above. The LP relaxation consists of nonnegativity together with the constraints ∑ _eδ(v)x_e ≤ 1 for each vertex v. A feasible solution to the LP relaxation is to take x_AB = 0.5, x_AF = 0, x_AG = 0.5, x_BC = 0.5, x_CD = 0, x_CG = 0, x_CH = 0.4, x_CJ = 0.1, x_DE = 0.2, x_DJ = 0.8, x_EF = 0.8, x_EJ = 0, x_FH = 0.2, x_GH = 0.4, and x_HJ = 0.
   1. Find a valid constraint for the matching problem that is violated by this solution.
   2. Assume the six diagonal edges each have weight two and the remaining 10 edges each have weight one. What is the maximum weight matching? Prove your solution is optimal.
3. Let S be the set of feasible solutions to the integer programming problem
   1. What is the Chvatal rank of the inequality 3x₁ + x₂ ≤ 12?
   2. Solve the LP relaxation of this problem. What is the Gomory cutting plane given by the objective function? What is the strong Gomory cutting plane given by the objective function, using the Gomory mixed integer cut? Express the constraints in terms of the original variables x₁ and x₂. (You may want to use AMPL to solve the LP relaxation. You can then get the reduced costs directly.)
4. Let S be the set of nonnegative integer points in ZZ³ satisfying the inequalities

   What is the dimension of S? Give a minimal description of the convex hull of S using inequalities and/or equalities.

5. Consider the maximum weight matching problem on a graph G = (V,E), where all edge weights are nonnegative. One possible separation routine is to search for connected components in the graph G = (V,E′), where E′ consists of all edges in E with x_e > 0 in the optimal solution to the LP-relaxation, and see if those components violate the odd set constraints. Use this in a cutting plane algorithm to solve the maximum weight matching problem on the graph below. Edge e_i has weight i. (Again, you may want to use AMPL to solve the LP relaxations. The initial AMPL model file is in http://www.rpi.edu/~mitchj/matp6620/hw3/hw3q5.mod0 and the data file is in
   http://www.rpi.edu/~mitchj/matp6620/hw3/hw3q5.dat0)
6. The Project:
   Along with your solutions to this homework, hand in a brief description of what you would like to do for the project part of this course.