Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Maximal Lattice-free convex sets and Cutting PlanesOptimization
|Speaker: ||Amitabh Basu, CMU|
|Location: ||1147 MSB|
|Start time: ||Mon, May 3 2010, 10:00AM|
Given a lattice of R^n, maximal lattice-free convex sets
(MLFCs) are convex sets which do not have any lattice point in their
interior and are maximal (with respect to set inclusion) with this
property. We characterize the structure of such convex sets. We next
establish a connection between MLFCs and cutting plane theory for mixed
integer linear programs. This has been a very recent line of research in
the Integer Programming community and has led to many new theorems in
cutting plane theory. I will try to give an overview of these results.
This is part of the VIGRE Research Focus Group on Optimization.