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
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.
and the sum of these constraints implies x_{u} + x_{v} + x_{w} ≤ 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.