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.