A Semidefinite Programming (SDP) relaxation, namely the Lovasz theta relaxation, yields strong upper bounds for the stable set problem. The same upper bounds can be obtained by an infinite family of linear inequalities, called orthonormal representation inequalities(ORIs). However, SDP can still be used to both separate and strengthen the ORIs. The resulting cutting plane algorithms are tested on standard benchmark instances and the results are presented.
Cutting planes for the Stable Set Problem by Semidefinite Programming
ROSSI, FABRIZIO;SMRIGLIO, STEFANO
2010-01-01
Abstract
A Semidefinite Programming (SDP) relaxation, namely the Lovasz theta relaxation, yields strong upper bounds for the stable set problem. The same upper bounds can be obtained by an infinite family of linear inequalities, called orthonormal representation inequalities(ORIs). However, SDP can still be used to both separate and strengthen the ORIs. The resulting cutting plane algorithms are tested on standard benchmark instances and the results are presented.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.
