Abstract: Semidefinite programming (SDP) is a subfield of convex optimization and a generalization of linear programming. In particular, in SDP one considers a positive semidefinite matrix variable instead of a non-negative vector variable when optimizing a linear objective function subject to linear constraints. Recently, the “exact subgraph” approach was introduced as a hierarchical scheme to get increasingly tight SDP relaxations of several NP-hard graph optimization problems. However, solving these SDP relaxations is a computational challenge because of the potentially large number of constraints.

In this talk, we introduce a computational framework for these SDP relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. We present theoretical convergence results and computational experiments on the Max-Cut, stable set and coloring problem, which show the excellent quality of the bounds obtained with this approach. We also discuss how to utilize these and other SDP based bounds when implementing a branch and bound algorithm for the stable set problem to compute the stability number of a graph and other theoretical and computational optimization aspects.