  The 'exact subgraph' approach was recently introduced as a hierarchical
scheme to get increasingly tight semidefinite programming relaxations of
several NP-hard graph optimization problems. Solving these relaxations is a
computational challenge because of the potentially large number of violated
subgraph constraints. We introduce a computational framework for these
relaxations designed to cope with these difficulties. We suggest a partial
Lagrangian dual, and exploit the fact that its evaluation decomposes into two
independent subproblems. This opens the way to use the bundle method from
non-smooth optimization to minimize the dual function. Computational
experiments on the Max-Cut, stable set and coloring problem show the efficiency
of this approach.
