Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization

S. Benson, Y. Ye and X. 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 various problems. Coupled with randomized and heuristic methods, we report computational results for approximating graph-partition and quadratic problems with dimension up to 3000. This finding, to the best of our knowledge, is the first computational evidence of the effectiveness of these approximation algorithms for solving large-scale problems. Check http://dollar.biz.uiowa.edu/col/ for free SDP software.

Working Paper, Applied Mathematics and Computational Sciences, University of Iowa, Iowa City, IA 52242, February, 1998.

Contact: yinyu-ye@uiowa.edu