##
Rank-Two Relaxation Heuristics for Max-Cut
and Other Binary Quadratic Programs

###
Samuel Burer, Renato Monteiro and Yin Zhang

Semidefinite relaxation for certain discrete optimization problems
involves replacing a vector-valued variable by a matrix-valued one,
producing a convex program while increasing the number of variables by
an order of magnitude. As useful as it is in theory, this approach
encounters difficulty in practice as problem size increases. In this
paper, we propose a rank-two relaxation approach and construct
continuous optimization heuristics applicable to some binary quadratic
programs, including primarily the Max-Cut problem but also others such
as the Max-Bisection problem. A computer code based on our rank-two
relaxation heuristics is compared with two state-of-the-art
semidefinite programming codes. We will report some rather intriguing
computational results on a large set of test problems and discuss
their ramifications.
Technical Report TR00-33
Department of Computational and Applied Mathematics
Rice University, Houston, Texas 77005

Contact: zhang@caam.rice.edu