On Solving Large-Scale Semidefinite Programming Problems: A Case Study of Quadratic Assignment Problem

Chih-Jen Lin and Romesh Saigal

Semidefinite programming (SDP) is a new topic in optimization and it has many potential applications. To date, computational issues that arise when solving large-scale SDP, using interior point methods, have not been investigated extensively. We use quadratic assignment problem (QAP) as a case and discuss algorithmic and implementation issues for solving large-scale SDP. The preconditioned conjugate gradient method is used to solve the fully dense linear system during each iteration. A new incomplete Cholesky factorization preconditioner is proposed and some numerical results with better lower bounds for QAP are obtained.

Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, December 1997

Contact: cjlin@engin.umich.edu