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.

An ellipsoidal relaxation for the stable set problem

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

Abstract

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