chvatal cuts

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

    On the Rational Polytopes with Chvatal Rank 1

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

    We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the … Read more