Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Kruempelmann, Jan; Weltge, Stefan
• 署名单位: Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0836
• 发表日期: 2017
• 页码: 1035-1062
• 关键词: strength

摘要

Lattice-free sets and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. The family of all integral lattice-free polyhedra that are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Z(d)-maximal. For fixed d, the family of Z(d)-maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane theory, one would like to have a classification of this family. This is a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra that are not properly contained in any other lattice-free set, which we call Z(d)-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of Z(d)-maximality and Z(d)-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, for d >= 4 there exist integral lattice-free polyhedra that are Z(d)-maximal but not Z(d)-maximal. We consider the remaining case d = 3 and prove that for integral lattice-free polyhedra the notions of Z(3)-maximality and Z(3)-maximality are equivalent. This allows to complete the classification of all Z(3)-maximal integral lattice-free polyhedra.