MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming
Homework 3.

Due: Thursday, March 4, 2021, by end of day.
Penalty for late homeworks: 10% for each day or part of a day.

The following graph G = (V,E) is used in question 1.


  1. Consider a node packing problem on the above graph, with each vertex having weight equal to 2 more than its degree. The LP relaxation includes the clique constraints vCxv 1 for each maximal clique C in the graph. The point xA = 0.4, xB = 0.6, xC = 0.4, xD = 0.5, xE = 0.4, xF = 0.5, xG = 0.1, xH = 0.4, and xJ = 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 the constraints
       t1  ≥  |x1 - x2|
   t2  ≥  |x1 + x2 - 1|
 t1,t2     integer
x1,x2     binary

    1. By considering the different possibilities for x, show that t1 + t2 1.
    2. The constraints can be modeled equivalently as
         t1  ≥    x1 -   x2
   t1  ≥  - x1 +   x2
   t2  ≥    x1 +   x2  -  1
   t2  ≥  - x1 -   x2  +  1
 t1,t2     integer
x1,x2     binary

      Show that the valid constraint t1 + t2 1 has Chvatal rank equal to 2.

  3. The optimal tableau to the linear programming relaxation of the integer program
    min   - x1 -  10x2                     min  - 36    +  32x3  +   1x4     17
s.t.    x1  +   2x2  ≤  14              s.t.  x1      +  4x3  -   4x4  =   2
      - x1 +   6x2  ≤  8          is            x2  +  18x3  +   18x4  =  114
             x1,x2  ≥  0,integer                          x,x ,x ,x   ≥  0
                                                          1 2  3  4

    where x3 and x4 are the slack variables in the two constraints. Find the Gomory and strong Gomory cutting planes implied by the two constraints. Express these constraints in terms of the original variables x1 and x2 and draw them on a graph of the feasible region.

  4. Let x Bn satisfy the constraints
    xi + xj ≥ 1 for 1 ≤ i < j ≤ n.

    Show that the constraint i=1nxi n - 1 is valid. Give a fractional point with 0 x e that satisfies the original n(n- 1)2 constraints but violates the new constraint. Show that the new constraint has Chvatal rank no larger than O(log n).

  5. The AMPL model of the LP relaxation of a random weighted node packing problem with 15 nodes is contained in the file

    The initial model contains only the adjacency constraint that just one endpoint of an edge can appear in the node packing. Pick a seed and then solve the problem using a cutting plane algorithm:

    1. Solve the LP relaxation.
    2. If the solution is integral, STOP.
    3. If necessary, add one or more valid inequalities to the LP. These inequalities can be clique inequalities or odd hole inequalities.
    4. Return to Step (a).

    (It is highly likely that you will need to use both clique inequalities and odd hole inequalities, and that these inequalities will be sufficient to solve the problem.)

    (Hint: The graph consists of the cycle 1 - 2 - 3 - 4 -- 14 - 15 - 1, plus some extra edges. You might be able to see the structure by displaying adjacency.)

  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.
    John Mitchell
    Amos Eaton 325
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.