Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
Arbeitsgruppe Faigle/Schrader
Dr. Alexander Engau
Universtiy of Colorado, Denver, USA
Department of Mathematical and Statistical Sciences
A semidefinite cutting-plane approach towards stable set
and the maximum-clique problem
The development of semidefinite programming (SDP) over the last 20
years was largely influenced by the design of efficient interior-point
algorithms for convex optimization and their wide applicability also
to NP-hard combinatorial problems. Often highlighted by the SDP
relaxation for the maximum-cut problem by Goemans and Williamson, for
this talk we consider a similarly well-known SDP relaxation for stable
set to compute the Lovász theta-number which gives upper and lower
bounds on the maximum-clique and the colouring number of a graph,
respectively. Although theoretical results have shown that this
relaxation can be strengthened using several classes of cutting
planes, efficient computational approaches remain largely unexplored.
We present our recent progress with a new interior-point cutting-plane
method that uses an improved mechanism for the dynamic addition and
removal of cut inequalities based on effective warm starts and
feasibility indicators at intermediate iterates. This approach does
not require to successively solve multiple relaxations and therefore
promises to solve most instances in significantly less time than
previous methods. This is joint work with Immanuel Bomze (Universität
Wien) and Miguel F. Anjos (University of Waterloo) who will focus on
the warm-start strategy and related concepts utilized by this method
in the Kolloquium on Friday, July 23.