Thorsten Bonato holds a Ph.D. in mathematics from the University of Heidelberg where he was a graduate student of Gerhard Reinelt in the Discrete and Combinatorial Optimization research group.

AG 1, AG 2, MMCI   Info

Expert Audience

English

45 Minutes

Saarbrücken

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, little research has been conducted for the cut polytope on arbitrary graphs. In this talk we present a new approach for generating valid, and sometimes facet defining, inequalities for the cut polytope on such graphs. Using specific graph transformations in combination with the subsequent projection and lifting of the separated inequalities, we are able to exploit algorithmic and structural results known for the cut polytope on complete graphs. Moreover, the graph transformations provide an efficient heuristic for separating so-called odd-cycle inequalities. Finally, we report some interesting computational results on a set of well-established benchmark problems.

Reference:
T. Bonato, M. Jünger, G. Reinelt, G. Rinaldi. Lifting and Separation Procedures for the Cut Polytope. Mathematical Programming A. 2013
http://link.springer.com/article/10.1007%2Fs10107-013-0688-2

Björn Andres

--email hidden

passcode not visible

logged in users only