A basic mixed integer set: the mixing set and its applications

Tuesday, July 26, 2005 - 2:45pm - 3:30pm
EE/CS 3-180
Laurence Wolsey (Université Catholique de Louvain)
Very little is known about the polyhedral structure of
even simple mixed integer programs. Here we study a very simple
set, called the mixing set. This set and valid inequalities for
it were proposed by Gunluk and Pochet in an effort to explain and
understand why the same procedure of mixing mixed integer
rounding (MIR) inequalities gave valid inequalities for many
different variants of the constant capacity lot-sizing problem,
and subsequently Miller and Wolsey took this abstraction a little
further by considering the intersection of mixing sets plus
certain additional constraints.

In this talk we pursue this effort at abstraction by considering
two abstract sets
that are generalizations of the mixing set.
We show that, modulo a
slight restriction, the convex hulls of both sets are obtained
with mixing inequalities. This is joint work with Michele Conforti
and Marco di Summa.

Turning back to lot-sizing, we show that a constant capacity
problem with production time windows, and surprisingly both a
multi-item problem with a joint set-up variable, and a class of
single item problems with varying capacities can also be solved by
mixing. The latter is joint work with Yves Pochet.

PDF file with formulations