##
Semidefinite Programming
Relaxations for the Graph Partitioning Problem

###
Henry Wolkowicz and Qing Zhao

A semidefinite programming, SDP, relaxation for the graph partitioning
problem, GP, is derived using the dual of the (homogenized) Lagrangian
dual of appropriate equivalent representations of GP. The special
structure of the relaxation is exploited in order to project the SDP
onto the {\em minimal face}, of the cone of positive semidefinite
matrices, which contains the feasible set. This guarantees that the
Slater constraint qualification holds; which allows for a primal-dual
interior-point solution technique. A {\em gangster operator} is the
key to providing an efficient representation of the constraints. An
incomplete preconditioned conjugate gradient method is used for
solving the large linear systems which arise when finding the Newton
direction.
Numerical results illustrate the efficacy of the SDP relaxations.
Research Report, University of Waterloo.

Contact: hwolkowi@orion.math.uwaterloo.ca