HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Cutting Planes and the Elementary Closure in Fixed Dimension

Alexander Bockmayr 1 Friedrich Eisenbrand
1 MODBIO - Computational models in molecular biology
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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$.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:56:30 PM
Last modification on : Friday, February 4, 2022 - 3:31:53 AM


  • HAL Id : inria-00101099, version 1



Alexander Bockmayr, Friedrich Eisenbrand. Cutting Planes and the Elementary Closure in Fixed Dimension. Mathematics of Operations Research, INFORMS, 2001, 26 (2), pp.304-312. ⟨inria-00101099⟩



Record views