Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Improving cuts by means of lifting

Mathematics of Data & Decisions

Speaker: Gennadiy Averkov, University of Magdeburg
Location: 1147 MSB
Start time: Tue, Jan 8 2019, 4:10PM

I will report on results obtained in a joint work with Amitabh Basu. 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, Cornuejols and Koeppe 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 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.