Gap Inequalities for the Max-Cut Problem

Speaker(s) Laura Galli Università di Pisa
Date 17 July 2013 – 16:30 to 17:00
Venue INI Seminar Room 1
Session Title Gap Inequalities for the Max-Cut Problem
Event [POPW01] Polynomial optimisation: workshop and summer school
Abstract 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.

Supported By