Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Separating valid inequalities from small integer programsAlgebra & Discrete Mathematics
|Speaker: ||Quentin Louveaux, Universite de Liege |
|Location: ||1147 MSB|
|Start time: ||Mon, Oct 21 2013, 11:00AM|
In this talk, we consider the question of generating deep cuts from integer
programs with a low number of rows.
The first part of the talk focuses on generating cuts for an integer program with
two rows, two integer variables not restricted in sign and n continuous variables.
To do that, we show how to reduce the complexity of setting up the polar of the integer hull
from a quadratic number of integer hull computations to a linear
number of integer hull computations. Furthermore we present an algorithm that
avoids computing all integer hulls. The polynomial running time
is not guaranteed but computational results show that the algorithm runs
quickly in practice.
The second part of the talk discusses the possibility of constructing a general
cut separator for any type of mixed integer model. Exploiting
this, we evaluate, from a computational perspective, the usefulness of cuts derived
from several types of multi-row relaxations. In particular, we present results with
four different strengthenings of the two-row intersection cut model, and multi-row
models with up to fifteen rows.
This is based on joint works with Laurent Poirrier and Domenico Salvagnin.