A comparative study of linear and semidefinite branch-and-cut<br/><br/>methods for solving the minimum graph bisection problem

Wednesday, November 19, 2008 - 2:00pm - 2:45pm
EE/CS 3-180
Christoph Helmberg (Technische Universität Chemnitz-Zwickau)
Joint work with Michael Armbruster (TU Chemnitz),
Marzena Fuegenschuh (TU Darmstadt), and
Alexander Martin (TU Darmstadt).

Semidefinite relaxations are known to deliver good approximations
for combinatorial optimization problems like graph bisection. Using
the spectral bundle method it is possible to exploit structural
properties of the underlying problem and to apply, even to sparse
large scale instances, cutting plane methods, probably the most
successful technique in linear programming. We set up a common
branch-and-cut framework for linear and semidefinite relaxations of
the minimum graph bisection problem. It incorporates
separation algorithms for valid inequalities presented in the recent
study by Armbruster, Fuegenschuh, Helmberg, and Martin 2007 of the
facial structure of the associated polytope. Extensive numerical
experiments show that the semidefinite branch-and-cut approach
outperforms the classical simplex approach on a clear majority of
the sparse large scale test instances. On instances from compiler
design the simplex approach is faster.
MSC Code: