Valid Inequalities for Integer Programs
John Mitchell

1 Polarity

Definition 1 The cone

Π  :=  {(π,π0) ∈ ℝn+1  : πTx - π0 ≤ 0  for all x ∈ Q}

is the polar of the polyhedron Q = {x ∈ ℝ+n : Ax b}.

Proposition 1 Let {xk} k∈K and {rj} j∈J be the extreme points and rays of Q. Then Π is the polyhedral cone defined by

πT xk - π   ≤  0  ∀k ∈ K
       T 0j
      π r   ≤  0  ∀j ∈ J.

Proposition 2 If dim(Q) = n and π0 then (π,π0) is an extreme ray of Π if and only if πT x π 0 defines a facet of Q.

2 Comparing Inequalities for Polyhedra

Assume we have two valid inequalities for x ∈ Q, namely

πTx  ≤   π0                                    (1)
 T
γ x  ≤   γ0.                                   (2)

Definition 2 The inequalities are equivalent if (γ,γ0) = μ(π,π0) for some μ > 0.

Definition 3 If the inequalities are not equivalent and if there exists μ > 0 such that γ μπ and γ0 μπ0 then

      n    T                   n    T
{x ∈ ℝ+  : γ x ≤  γ0} ⊆ {x ∈  ℝ+  : π x ≤ π0 }

and (2) dominates or is stronger than (1). A maximal valid inequality is one that is not dominated by any other.

Proposition 3 Let πT x π 0 be a valid inequality for Q = {x ∈ ℝ+n : Ax b}. If Q then πT x π 0 is either equivalent to or dominated by an inequality of the form uT Ax uT b for some u ∈ ℝ+m.

3 Chvatal-Gomory Rounding Procedure

Let P = {x ∈ ℝ+n : Ax b} and S = P n. Assume A is m×n. Denote the entries of A by a ij. The Chvatal-Gomory rounding procedure generates valid linear inequalities for S from valid linear inequalities for P as follows:

  1. Choose multipliers u ∈ ℝ+m and construct the following inequality that is valid for P:
     T        T
u Ax  ≤  u b,

    or equivalently

    ∑n  ( ∑m      )        ∑m
          uiaij   xj ≤      uibi.
j=1   i=1              i=1
    (3)

  2. Round down the left hand side, giving an inequality that is still valid for P, since it is weaker than the original inequality (3):
        ⌊         ⌋
∑n    ∑m               ∑m
          uiaij  xj ≤      uibi.
j=1   i=1              i=1

  3. Round down the right hand side, giving an inequality that is valid for S, since the left hand side must take an integral value:
         ⌊        ⌋        ⌊        ⌋
∑ n   ∑m                ∑m
          uiaij  xj ≤       uibi .
 j=1    i=1                i=1

Theorem 1 Every valid linear inequality for S can be obtained through a finite number of applications of the Chvatal-Gomory rounding procedure.

It may take many rounds of application of the procedure to produce a particular inequality. The number of rounds is called the Chvatal rank, which is defined in an inductive manner.

Definition 4 A valid linear inequality πT x π 0 for S has Chvatal rank 0 if it is equivalent to or dominated by a nonnegative linear combination of the inequalities defining P. It has Chvatal rank k if

Theorem 1 is equivalent to the statement that every valid linear inequality for S has finite Chvatal rank.