Christoph
Helmberg
Title:
Experiments with linear and semidefinite relaxations for
solving the minimum graph bisection problem
Abstract:
Given a graph $G=(V,E)$ with node weights $f_v \in
\mathbb{N}_0,\,v\in V$,
and some number $F\in \mathbb{N}_0$, the convex hull of the
incidence vectors of all cuts $\delta(S),\, S\subseteq V$ with
$f(S)\le F$ and $f(V\setminus S)\le F$ is called the {\em bisection
cut polytope}. We study the facial structure of this polytope
which shows up in many graph partitioning problems with applications
in VLSI-design or frequency assignment.
We give necessary and in some cases sufficient conditions
for the \emph{knapsack tree inequalities} introduced
in Ferreira et al.~1996 to be facet-defining. Then we generalize
these inequalities to the richer class of \emph{bisection knapsack walk
inequalities} by exploiting that each cut intersects each cycle in an
even number
of edges. Furthermore, we present a new class of inequalities that live
on
non-connected substructures, have non-linear right-hand sides and
strengthen
the bisection knapsack walk inequalities. We show that the
supporting hyperplanes of the convex envelope of this non-linear
right-hand sides
correspond to the faces of the socalled {\em cluster weight polytope},
for which we give a complete description under certain conditions.
Finally, we
incorporate the presented inequalities in a branch-and-cut framework and
discuss their interaction with the linear and semidefinite relaxation.
Slides