# MPI-I-1999-2-008

## Cutting planes and the elementary closure in fixed dimension

### Bockmayr, Alexander and Eisenbrand, Friedrich

**MPI-I-1999-2-008**. December** **1999, 12 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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$.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 247 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/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},`

`}`