MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


On the Chvátal rank of polytopes in the 0/1 cube

Bockmayr, Alexander and Eisenbrand, Friedrich

September 1997, 12 pages.

Status: available - back from printing

Given a polytope $P \subseteq \mathbb{R}^n$, the Chv\'atal-Gomory procedure computes iteratively the integer hull $P_I$ of $P$. The Chv\'atal rank of $P$ is the minimal number of iterations needed to obtain $P_I$. It is always finite, but already the Chv\'atal rank of polytopes in $\mathbb{R}^2$ can be arbitrarily large. In this paper, we study polytopes in the 0/1~cube, which are of particular interest in combinatorial optimization. We show that the Chv\'atal rank of a polytope $P \subseteq [0,1]^n $ in the 0/1~cube is at most $6 n^3 \log n$ and prove the linear upper and lower bound $n$ for the case $P\cap \mathbb{Z}^n = \emptyset$.
Categories / Keywords:
combinatorial optimization, integer programming, cutting plane, polytope

  • Attachement: ATTYGU65 (186 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Bockmayr, Alexander and Eisenbrand, Friedrich},
  TITLE = {On the {Chv{\'a}tal} rank of polytopes in the 0/1 cube},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-2-009},
  MONTH = {September},
  YEAR = {1997},
  ISSN = {0946-011X},