Rank Bounds and Integrality Gaps for Cutting Planes Procedures

We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to Lova 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 Cutting Planes and Lova ́sz- Schrijver 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 CP or LS procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap. Secondly, we give unsatisfiable examples that have constant rank CP and LS proofs but that require linear rank Resolution proofs. Thirdly, we give examples where the CP rank is O(logn) 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 with polynomial-size CP/LS proofs, but requiring linear rank.