chvatal rank

Chvatal rank in binary polynomial optimization

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , , ,

    Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more

    On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvatal Rank

  • Gérard Cornuéjols
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0,1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of … Read more