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

Gennadiy Averkov (), Jan Krümpelmann () and Stefan Weltge ()
Additional contact information
Gennadiy Averkov: Otto-von-Guericke-Universität Magdeburg, 39106 Magdeburg, Germany
Jan Krümpelmann: Otto-von-Guericke-Universität Magdeburg, 39106 Magdeburg, Germany
Stefan Weltge: ETH Zürich, 8092 Zürich, Switzerland

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1035-1062

Abstract: 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 ℤ d -maximal. For fixed d , the family of ℤ 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 ℝ d -maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of ℤ d -maximality and ℝ 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 ℤ d -maximal but not ℝ d -maximal. We consider the remaining case d = 3 and prove that for integral lattice-free polyhedra the notions of ℝ 3 -maximality and ℤ 3 -maximality are equivalent. This allows to complete the classification of all ℤ 3 -maximal integral lattice-free polyhedra.

Keywords: classification; cutting planes; integral polyhedra; lattice-free sets; mixed-integer optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0836 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1035-1062

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().