GEORGE MASON UNIVERSITY
DEPARTMENT OF MATHEMATICAL SCIENCES
COLLOQUIUM MARCH 20, 2009

Speaker: Francois Margot, Carnegie Mellon University

Title: On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints

Abstract: We consider an infinite relaxation of the mixed integer linear program with two integer variables, nonnegative continuous variables and two equality constraints, and we give a complete characterization of its facets, classifying them into three types of nontrivial facets: split, triangle or quadrilateral inequalities.

We compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.

Joint work with A. Basu (CMU), G. Cornuejols (CMU), P. Bonami (LIF, MArseille)

Time: Friday, March 20, 3:30-4:20 p.m.

Place: Science and Technology Building I, Room 242

Refreshments will be served before the talk at 3:00 p.m. in Room 222.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491