Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Friday, 21 February 2014
Time:10:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4
Room:633
Abstract
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

Contact
Name(s):Björn Andres
EMail:andres@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
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.