Semidefinite Programming for Combinatorial Optimization
This book offers a self-contained introduction to the field of
semidefinite programming, its applications in combinatorial
optimization, and its computational methods.
We equip the reader with the basic results from linear algebra on
positive semidefinite matrices and the cone spanned by them. Starting
from linear programming, we introduce semidefinite programs and
discuss the associated duality theory. We then turn to semidefinite
relaxations of combinatorial optimization and illustrate their
In the second half we deal with computational methods for solving
semidefinite programs. First, the interior point approach, its
iteration complexity, and implementational issues are discussed.
Next, we explain in great detail the spectral bundle method, which is
particularly suited for large scale semidefinite programming.
One of the most successful techniques in integer linear programming is
the cutting plane approach which improves an initial relaxation by
adding violated inequalities. We explore possibilities to combine the
two solution methods with the cutting plane approach in order to
strengthen semidefinite relaxations of combinatorial optimization
Habilitationsschrift, TU Berlin, January 2000.
ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin,
Takustrasse 7, D-14195 Berlin, Germany,