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 [1].

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

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