Tutte seminar - Laurent Poirrier

Multi-row Approaches to Cutting Plane Generation

Abstract: 

We cover two topics in the generation of multi-row cutting planes.

In the first one, we present a separation method for two-row cuts.
Two-row cuts are intersection cuts from two rows of a simplex tableau
describing the LP relaxation of the problem. The specificity of the approach adopted here is that it does not rely on an "infinite relaxation" point of view and generate intersection cuts from fixed lattice-free sets. Instead, given a fractional point, it aims at always finding a most violated
facet-defining inequality for the two-row model. This is known to be
achievable by optimizing over the polar set of the integer hull of the
model. We develop an improvement on this approach, by means of a polyhedron that is equivalent to the polar for our purpose, but has a more compact representation. We perform row-generation in order to avoid the costly computations of integer hulls of two-dimensional cones, and provide a simple oracle for finding violated constraints. An implementation of the resulting algorithm performs separation of two-row cuts in a few milliseconds on average, on the standard MIPLIB 3 and 2003 test sets.

While this two-row separator is quick, the measurements of the computational usefulness of the cuts do not yield satisfactory results.
Since all the cuts generated are facet-defining, this might suggest that the underlying two-row models are too weak. This observation prompted an attempt to evaluate the strength of various multi-row relaxations, on small instances, using a generic separator. To that end, a separator is developed, which is able to compute facet-defining inequalities from arbitrary (yet reasonably small) mixed-integer sets. A row-generation approach is again adopted, but this time the slave part consists in the resolution of a mixed-integer problem instead of a closed-form oracle. Some interesting computational tricks are necessary in order to speed up the inherently hard computations.