Cutting Planes from a Convex Quadratic Relaxation of the Stable Set Problem

"A great deal of research has been focused on finding both linear and semidefinite relaxations for the Stable Set problem, but the resulting branch-and-bound algorithms have not been completely successful in practice. We propose an approach based on the construction of an ellipsoid that (i) contains the Stable Set Polytope, and (ii) whose associated upper bound equals the Lovász theta number. This ellipsoid is then exploited to derive strong (linear) cutting planes. Extensive computational results demonstrate that embedding these cutting planes in a branch-and-cut framework can be profitable."