Publications

S. J. Benson and Y.Ye,, "DSDP3: Dual Scaling Algorithm for General Positive Semidefinite Programming," Preprint ANL/MCS-P851-1000, February 2001. [pdf]

We implement a dual scaling algorithm for positive semidefinite programming to handle a broader class of problems than could be solved with previous implementations of the algorithm. With appropriate representations of constraint matrices, we can solve general semidefinite programs and still exploit the structure of large-scale combinatorial optimization problems. Computational results show that our preliminary implementation is competitive with primal-dual solvers on many problems requiring moderate precision in the solution and is superior to primal-dual solvers for several types of problems.