Return to Colloquia & Seminar listing
Maximal Lattice-free convex sets and Cutting Planes
Optimization| 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.