Cutting planes and the elementary closure in fixed dimension

• 成果类型: Article
• 署名作者: Bockmayr, A; Eisenbrand, F
• 署名单位: Universite de Lorraine; Max Planck Society
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.26.2.304.10555
• 发表日期: 2001
• 页码: 304-312
• 关键词: integer points; chvatal rank; polytopes

摘要

The elementary closure P' of a polyhedron P is the intersection of P with all its Gomory-Chvatal 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(1) include the facets of P'. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q(1).