Seminar: A 3-Slope Theorem for the Infinite Relaxation in the Plane

Wednesday, April 6, 2011 (12:00pm)
•Title: A 3-Slope Theorem for the Infinite Relaxation in the Plane
•Speaker: Marco Molinaro, CMU ACO program •Location: ISyE executive classroom
We consider the infinite relaxation of the corner polyhedron with 2 rows. For the 1-row case, Gomory and Johnson proved in their seminal paper a sufficient condition for a minimal function to be extreme, the celebrated 2-Slope Theorem. Despite increased interest in understanding the multiple row setting, no generalization of this theorem was known for this case. We present an extension of the 2-Slope Theorem for the case of 2 rows by showing that minimal 3-slope functions satisfying an additional regularity condition are extreme. Moreover, we show that this regularity condition is necessary, unveiling a structure which is only present in the multi-row setting.
This is a joint work with Gerard Cornuejols.