MPI-INF/SWS Research Reports 1991-2017

# MPI-I-1999-2-008

## Cutting planes and the elementary closure in fixed dimension

### Bockmayr, Alexander and Eisenbrand, Friedrich

#### December 1999, 12 pages.

.
##### Status: available - back from printing

The elementary closure \$P'\$ of a polyhedron \$P\$ is the intersection of \$P\$ with all its Gomory-Chvátal cutting planes. \$P'\$ is a rational polyhedron provided that \$P\$ is rational. The known bounds for the number of inequalities defining \$P'\$ are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If \$P\$ is a simplicial cone, we construct a polytope \$Q\$, whose integral elements correspond to cutting planes of \$P\$. The vertices of the integer hull \$Q_I\$ include the facets of \$P'\$. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of \$Q_I\$.

• Attachement: MPI-I-1999-2-008.ps (247 KBytes)

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

BibTeX
@TECHREPORT{BockmayrEisenbrandMPI-I-1999-2-008,
AUTHOR = {Bockmayr, Alexander and Eisenbrand, Friedrich},
TITLE = {Cutting planes and the elementary closure in fixed dimension},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-1999-2-008},
MONTH = {December},
YEAR = {1999},
ISSN = {0946-011X},
}