An algorithm for the separation of two-row cuts

We consider the question of finding deep cuts from a model constructed with two rows of a simplex tableau. To do that, we show how to reduce the complexity of setting up the polar of such model from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore we present an algorithm that avoids computing integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.

Citation

March 2010, revised September 2012. To appear in Mathematical Programming A.

Article

Download

View An algorithm for the separation of two-row cuts