Minimal Valid Inequalities and Maximal Lattice-Free Convex Sets
<-- Return to the list
Date: 12-16-2008
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Gerald Cornuejols, Carnegie Mellon University
Location: 303 Mudd
ABSTRACT
In this talk we study valid inequalities in integer programming. We show that, for a variant of Gomory's corner polyhedron, minimal valid inequalities correspond to maximal lattice-free convex sets. In the plane these sets are splits, triangles and quadrilaterals. We compare the strength of the three corresponding families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well-defined sense, triangle and quadrilateral inequalities provide a good approximation of the integer hull whereas the approximation produced by splits may be arbitrarily bad.
This talk is based on joint work with Borozan, Basu, Bonami and Margot.
BIO
Gerard Cornuejols is IBM professor of Operations Research at Carnegie Mellon University, and University Professor. He was awarded the Lanchester Prize in 1977, the Fulkerson Prize in 2000 and the SIAM Outstanding Paper Prize in 2004.