Showing Chvatal Rank is at least Two
John Mitchell

Let

            n                           n
P := {x ∈ ℝ + : Ax ≤ b},     S := P ∩ ℤ  .

Let

πT x ≤ π0
(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

(uT A )x ≤  uTb,   with u ≥ 0.

The rounddown of such an inequality dominates (1) if

⌊AT u⌋ ≥ π   and    ⌊bTu ⌋ ≤ π0.

Since π and π0 are integer, this is equivalent to saying that (1) has rank no greater than one if

  T                T
A  u ≥ π    and   b u <  π0 + 1.

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:

minu         bTu
subject to  AT u  ≥   π
               u  ≥   0
(2)

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

maxx        πTx
subject to   Ax   ≤  b
              x   ≥  0.
(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

P =  {x ∈ ℝn : xu + xv ≤ 1∀(u,v) ∈ E, 0 ≤ xu ≤ 1 ∀u ∈ V }.

For any clique C V , we have the valid inequality

∑
    xu ≤ 1.
u∈C
(4)

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

References

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