Gap Inequalities for the Max-Cut Problem
Seminar Room 1, Newton Institute
AbstractLaurent & Poljak introduced an interesting class of valid inequalities for the cut polytope, called gap inequalities. The gap inequalities are remarkably general, including several other important classes of inequalities (including some known to define facets) as special cases. Unfortunately, however, computing the right-hand side of a gap inequality, for a given left-hand side, is NP-hard. This suggests that it would be difficult to use gap inequalities as cutting planes. Perhaps for this reason, the inequalities have received little attention from researchers.
In this talk, we present some recent progress on the gap inequalities. In particular:
1. We show how to define gap inequalities for a much more general class of problems (non-convex Mixed-Integer Quadratic Programs).
2. We prove several results concerned with the computational complexity of various problems related to gap inequalities.
3. We present the first ever finite separation algorithm for the gap inequalities.
4. We present some computational results obtained when using gap inequalities as cutting planes.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.