Efficient Implementation of SDP Relaxat...

The stable set problem is among the most prominent problems of combinatorial optimization. Given a graph, it asks for a maximum stable set, that is a set of vertices such that no two vertices are adjacent of largest possible cardinality. The cardinality of such a maximum stable set is called the stability number.

 The stable set problem is NP-complete, hence there is no polynomial time algorithm to solve the stable set problem exactly unless P=NP. In order to solve the stable set problem exactly with a branch-and-bound algorithm tight upper bounds on the stability number are required. One possible upper bound is given by the Lovász theta function, which can be computed as semidefinite program (SDP). In order to improve this upper bound one can add so-called exact subgraph constraints (ESCs) for some wisely chosen subgraphs into this SDP. For a certain subgraph, the ESC ensures that the submatrix of the calculation of the Lovász theta function corresponding to the subgraph is contained in the convex hull of all stable set matrices of the subgraph.

 The aim of this thesis it to computationally exploit ESCs in order to get improved upper bounds on the stability number. Towards that end three different possibilities to include the ESCs into the SDP are presented. Furthermore a specialized solution algorithm based on the bundle method in order to solve the resulting SDP fast is developed. Moreover methods to determine the subgraphs for which the ESC should be included are discussed.