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.

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

ROSSI, FABRIZIO;SMRIGLIO, STEFANO
2010-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/39663
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact