Semidefinite programming relaxations for the graph partitioning problem

A new semidefinite programming, SDP, relaxation for the general graph parti tioning problem, GP, is derived. The relaxation arises from the dual of the (homogenized) Lagrangian dual of an appropriate quadratic representation o f GP. The quadratic representation includes a representation of the 0,1 con straints in GP. The special structure of the relaxation is exploited in ord er to project onto the minimal face of the cone of positive-semidefinite ma trices which contains the feasible set. This guarantees that the Slater con straint qualification holds, which allows for a numerically stable primal-d ual interior-point solution technique. A gangster operator is the key to pr oviding an efficient representation of the constraints in the relaxation. A n incomplete preconditioned conjugate gradient method is used for solving t he large linear systems which arise when finding the Newton direction. Only dual feasibility is enforced, which results in the desired lower bounds, b ut avoids the expensive primal feasibility calculations. Numerical results illustrate the efficacy of the SDP relaxations. (C) 1999 Elsevier Science B .V. All rights reserved.