Strong lift-and-project cutting planes for the Stable Set Problem

Given a graph G = (V,E), QSTAB(G) denotes the polytope defined by the clique and non-negativity inequalities. The application of the Lovasz-Schrijver M(k,k) lifting operator to QSTAB(G) yields a strong non-compact linear relaxation of the stable set problem, as illustrated in Giandomenico et al.(2008). In particular, the upper bounds obtained by optimizing over M(QSTAB(G),QSTAB(G)) are comparable, sometimes better, than the Lovasz theta number \theta(G) as well as stronger bounds computed by semidefinite programming techniques (Burer, Vandenbussche 2006, Gruber and Rendl 2003, Dukanovic and Rendl 2007). In this talk we illustrate the projection of M(QSTAB(G),QSTAB(G)) onto the original space by the Benders decomposition. An extensive computational experience is presented showing that the resulting cutting planes are effective and the method promising for practical implementations.