"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."

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

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

Abstract

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

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/88599
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact