Showing Chvatal Rank is at least Two
be a valid inequality for S. Here is an argument for showing the inequality has Chvatal rank at least 2. The argument comes from Proposition 2.17 in section II.1.2 of .
We use a proof by contradiction, so we assume the inequality has rank no larger than 1. Then the inequality is dominated by the rounddown of a valid inequality for P. Valid inequalities for P have the form
The rounddown of such an inequality dominates (1) if
Since π and π0 are integer, this is equivalent to saying that (1) has rank no greater than one if
for some u ≥ 0. Equivalently, (1) has Chvatal rank no greater than one if and only if the following linear program has optimal value strictly smaller than π0 + 1:
We can express the requirement in terms of the dual LP, which has feasible region P:
Thus, we have the following proposition:
We consider the node packing problem on a graph G = (V,E). The initial polyhedron is
For any clique C ⊆ V , we have the valid inequality
We investigate the Chvatal-Gomory rank of this inequality for cliques of various sizes.
and the sum of these constraints implies xu + xv + xw ≤ 1.5. Thus,
so by part 1 of the proposition, constraint (4) has rank no larger than 1 for this clique.
Thus, by part 2 of the proposition, constraint (4) has rank at least 2 for this clique.