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

Cutting Planes and the Elementary Closure in Fixed Dimension

Alexander Bockmayr 1 Friedrich Eisenbrand
1 PROTHEO - Constraints, automatic deduction and software properties proofs
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 :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:40:38 AM
Last modification on : Friday, February 4, 2022 - 3:31:28 AM


  • HAL Id : inria-00098944, version 1



Alexander Bockmayr, Friedrich Eisenbrand. Cutting Planes and the Elementary Closure in Fixed Dimension. [Intern report] 99-R-362 || bockmayr_99a, 1999, 12 p. ⟨inria-00098944⟩



Record views