Optimization Online


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

Gerard Cornuejols(gc0v***at***andrew.cmu.edu)
Dabeen Lee(dabeenl***at***andrew.cmu.edu)

Abstract: 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 the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvatal rank is at most 3; and when it has tree width 2, the Chvatal rank is at most 4. We also give polyhedral decomposition theorems when this graph has a vertex cutset of size one or two.

Keywords: Integer programming, Chvatal rank, Chvatal cuts

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Mathematical Programming B, 2018

Download: [PDF]

Entry Submitted: 08/07/2018
Entry Accepted: 08/07/2018
Entry Last Modified: 08/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society