Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Corner Polyhedra and Maximal Lattice-free Convex Bodies: A Fresh Geometric Approach to Cutting Plane Theory


Speaker: Amitabh Basu, UC Davis
Location: 1147 MSB
Start time: Mon, Dec 19 2011, 2:10PM

I will present my work on techniques which have the potential to create the next methodological breakthrough in solving general discrete optimization problems. The talk will focus on my work in cutting plane theory for Mixed-Integer Linear Programming. I will present a framework which unifies previous methods in cutting planes and provides new, and potentially much stronger, cutting plane ideas. This line of work combines the insights behind Gomory's Corner Polyhedron and Balas' Intersection Cuts, using tools from convex analysis, polyhedral geometry and the geometry of numbers. This line of work has initiated intense research activity in the integer programming community. The ultimate hope is to achieve the next leap in improving Integer Programming algorithms.