Affordable Access

Cutting planes and the parameter cutwidth.

Publication Date
  • Mathematics


We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. Considering CP as a propositional refutation system, one can see that the cutwidth of a CNF contradiction F is always bound above by the Resolution width of F. We provide an example proving that the converse fails: there is an F which has constant cutwidth, but has Resolution width Ω(n). Following a standard method for converting an FO sentence ψ, without finite models, into a sequence of CNFs, F ψ,n , we provide a classification theorem for CP based on the sum cutwidth plus rank. Specifically, the cutwidth+rank of F ψ,n is bound by a constant c (depending on ψ only) iff ψ has no (infinite) models. This result may be seen as a relative of various gap theorems extant in the literature.

There are no comments yet on this publication. Be the first to share your thoughts.