Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Maximal Lattice-free convex sets and Cutting Planes


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.