Volume 2 (2006) Article 4 pp. 65-90
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Published: March 25, 2006
[PDF (286K)]    [PS (554K)]    [PS.GZ (132K)]
[Source ZIP]
Keywords: cutting planes, proof complexity, approximation algorithms
ACM Classification: G.1.6, F.4.1, F.1.3
AMS Classification: 68Q25, 03F20, 90C05, 90C09

Abstract: [Plain Text Version]

$\def\GC{\mbox{GC}} \def\LS{\mbox{LS}}$

We present a new method for proving rank lower bounds for the cutting planes procedures of Gomory and Chvátal ($\GC$) and Lovász and Schrijver ($\LS$), when viewed as proof systems for unsatisfiability. We apply this method to obtain the following new results: First, we prove near-optimal rank bounds for $\GC$ and $\LS$ proofs for several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of $\GC$ or $\LS$ procedures when applied to the standard MAXSAT linear relaxation does not reduce the integrality gap. Second, we give unsatisfiable examples that have constant rank $\GC$ and $\LS$ proofs but that require linear rank Resolution proofs. Third, we give examples where the $\GC$ rank is $O(\log n)$ but the $\LS$ rank is linear. Finally, we address the question of size versus rank; we show that, for both proof systems, rank does not accurately reflect proof size. Specifically, there are examples which have polynomial-size $\GC$/$\LS$ proofs but require linear rank.