When : Wednesday, May 11, 2005, 3-4PM
Where: ESRC Shephard Room (Etcheverry Hall, 3rd Floor)

=============================================================
Valid inequalities for (mixed) integer programs
Oktay Gunluk, Math. Sciences, IBM Research
=============================================================

In the first part of the talk, we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities "two-step MIR inequalities" as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice.

In the second part, we study the shooting experiment of Gomory which computationally identifies "important" facets of the cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We present computational results that suggest that MIR and two-step MIR inequalities are important.

This talk summarizes results from the following two papers co-authored with Sanjeeb Dash: Paper 1: Valid inequalities based on simple mixed-integer sets Paper 2: Valid inequalities based on the interpolation procedure both available at: http://www.research.ibm.com/people/o/oktay/