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.