The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Gap Inequalities for the Max-Cut Problem

Galli, L (UniversitÓ di Pisa)
Wednesday 17 July 2013, 16:30-17:00

Seminar Room 1, Newton Institute


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.


[pdf ]


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.

Back to top ∧