Lifting properties of maximal lattice-free polyhedra

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Basu, Amitabh
• 署名单位: Otto von Guericke University; Johns Hopkins University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0865-6
• 发表日期: 2015
• 页码: 81-111
• 关键词: polytopes; variables; sets

摘要

We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346-355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterative construction to get maximal lattice-free polyhedra with the unique-lifting property in arbitrary dimensions. This single construction not only obtains all previously known polyhedra with the unique-lifting property, but goes further and vastly expands the known list of such polyhedra. Finally, we extend characterizations from Basu et al. (2012) about lifting with respect to maximal lattice-free simplices to more general polytopes. These nontrivial generalizations rely on a number of results from discrete geometry, including the Venkov-Alexandrov-McMullen theorem on translative tilings and characterizations of zonotopes in terms of central symmetry of their faces.