Several hard combinatorial optimization problems, such as Max-Cut or Quadratic Assignment can be approximated nicely by Semidefinite Programs (SDP). These relaxations can be further improved by including combinatorial cutting planes, resulting in huge SDPs.

We use the bundle method from nonsmooth optimization to tackle these SDPs. The idea consists in identifying a basic model, and taking the Lagrange dual of the remaining constraints.

We discuss some practical issues like finding good primal solutions, and identifying important cutting planes.

Finally, we present computational results of this approach applied to the max-cut relaxation given by the basic SDP model intersected with the metric polytope, and SDP relaxations of the Quadratic Assignment Problem.