Showing Chvatal Rank is at least Two
John Mitchell

Let Let (1)

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: (2)

We can express the requirement in terms of the dual LP, which has feasible region P: (3)

Thus, we have the following proposition:

Proposition 1

1.
If the integer part of the optimal value of (3) is no greater than π0 then inequality (1) has Chvatal-Gomory rank at most one.
2.
If the optimal value of (3) is at least π0 + 1 then inequality (1) has Chvatal-Gomory rank at least two.

Example

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 (4)

We investigate the Chvatal-Gomory rank of this inequality for cliques of various sizes.

• Let C = {u,v,w} be a clique of size 3 in G. The polyhedron P includes the constraints 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.

• Let C V be a clique of cardinality 4. The point xv = 0.5 for all v V is in P, so Thus, by part 2 of the proposition, constraint (4) has rank at least 2 for this clique.

### References

   G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley, New York, 1988.