Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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.