Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Wagner, Christian; Weismantel, Robert
• 署名单位: Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0510
• 发表日期: 2011
• 页码: 721-742
• 关键词: integer variables; simplex tableau; cutting planes; convex-sets; polytopes; points; cuts; inequalities; simplices; strength

摘要

A convex set with nonempty interior is maximal lattice-free if it is inclusion maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron P in R-d is the smallest natural number s such that sP is an integral polyhedron. In this paper we show that, up to affine mappings preserving Z(d), the number of maximal lattice-free rational polyhedra of a given precision s is finite. Furthermore, we present the complete list of all maximal lattice-free integral polyhedra in dimension three. Our results are motivated by recent research on cutting plane theory in mixed-integer linear optimization.