Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Lifting and Separation Procedures for the Cut Polytope
Speaker:Thorsten Bonato
coming from:University of Heidelberg
Speakers Bio: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.
Event Type:Talk
Visibility:D1, D2, MMCI
We use this to send out email in the morning.
Level:Expert Audience
Date, Time and Location
Date:Friday, 21 February 2014
Duration:45 Minutes
Building:E1 4
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.

T. Bonato, M. Jünger, G. Reinelt, G. Rinaldi. Lifting and Separation Procedures for the Cut Polytope. Mathematical Programming A. 2013

Name(s):Björn Andres
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Björn Andres, 02/07/2014 01:58 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Björn Andres, 02/07/2014 01:58 PM -- Created document.