Sparse Two-Row Cuts and an Algorithm for the Separation Problem

We propose a systematic way to generate sparse cuts from multiple rows of the simplex tableau. We also discuss the question of separation for a multi-row model. To this end, we consideer the polar system allowing to generate valid inequalities. In order to avoid generating the large number of constraints of the polar, we consider a reduced version of it that we dynamically extend. Checking the validity of an inequality is done geometrically. Computational results showing the efficiency of the algorithm are presented. This is a joint work with Laurent Poirrier.