• search hit 74 of 1117
Back to Result List

Notions of maximality for integral lattice-free polyhedra - the case of dimension three

  • Lattice-free sets (convex subsets of Rd without interior integer points) and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. Notably, the family of all integral lattice-free polyhedra which are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Zd-maximal. It is known that, for fixed d, the family Zd-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. However, this turns out to be a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra which are not properly contained in any other lattice-free set, which we call Rd-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of Zd-maximality and Rd-maximality areLattice-free sets (convex subsets of Rd without interior integer points) and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. Notably, the family of all integral lattice-free polyhedra which are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Zd-maximal. It is known that, for fixed d, the family Zd-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. However, this turns out to be a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra which are not properly contained in any other lattice-free set, which we call Rd-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of Zd-maximality and Rd-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, Nill and Ziegler (2011) showed that for dimension d≥4, there exist polyhedra which are Zd-maximal but not Rd-maximal. In this article, we consider the remaining case d=3 and prove that for integral polyhedra the notions of R3-maximality and Z3-maximality are equivalent. As a consequence, the classification of all R3-maximal integral polyhedra by Averkov, Wagner and Weismantel (2011) contains all Z3-maximal integral polyhedra.show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Gennadiy Averkov, Jan Krümpelmann, Stefan Weltge
URL:https://arxiv.org/abs/1509.05200
Title of the source (English):arXiv.org : (math)
Document Type:Scientific journal article peer-reviewed
Language:English
Year of publication:2015
Number of pages:45
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Algorithmische Mathematik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.