Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization (Revision)

Steven Benson, Yinyu Ye, and Xiong Zhang

We use the semidefinite relaxation to approximate combinatorial and quadratic optimization problems subject to linear, quadratic, as well as boolean constraints. We present a dual potential reduction algorithm and show how to exploit the sparse structure of the relaxation. We report computational results for solving the Max-Cut semidefinite program whose dimension is up-to 5000.

In the revision, we have added the computational result for solving the Max-Cut semidefinite programs of the G-set problems into the working paper. The G-set problems were generated by RUDY, a machine independent graph generator written by G. Rinaldi. This set of graph problems has been tested by a number of researchers. Our code was run on a Pentium-PC/233(MHZ) with 64M memory plus additional virtual hard-disk memory.

Working Paper, Department of Management Science, University of Iowa, IA, 52242, USA.