skip to content

Gap Inequalities for the Max-Cut Problem

Presented by: 
L Galli Università di Pisa
Wednesday 17th July 2013 - 16:30 to 17:00
INI Seminar Room 1
Laurent & 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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons