MPI-I-97-2-009

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

Bockmayr, Alexander and Eisenbrand, Friedrich

MPI-I-97-2-009. September 1997, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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$.
Acknowledgement:
Categories / Keywords: combinatorial optimization, integer programming, cutting plane, polytope
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	186 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-2-009

BibTeX
@TECHREPORT{BockmayrEisenbrand97, 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},}