An ellipsoidal relaxation for the stable set problem

The stable set problem gives rise to difficult integer programs. One major reason is that linear relaxations provide weak bounds (even though at low computational cost), while semidefinite relaxations give good (sometimes excellent) bounds but too demanding to compute. The Lov ́asz theta relaxation seems to provide the right compromise between strength and computational tractability, even if embedding it within an enumeration scheme is not straightforward. In this talk, we present a new convex programming relaxation having the theta bound as optimal value, whose feasible region takes the form of an ellipsoid. In principle, this allows us to resort to a branch-and-cut algorithm in which each subproblem includes one convex quadratic constraint. However, the el- lipsoid can also be used to derive valid inequalities for the stable set polytope: a hyperplane tangent to the ellipsoid can be exploited to generate strong cutting planes by a sequential strengthening procedure. We discuss the performance of the resulting (LP-based) branch-and-cut algorithm through extensive experiments.