Submitted manuscript, 212 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem
AU - Giandomenico, M
AU - Letchford, A N
AU - Rossi, F
AU - Smriglio, S
PY - 2009
Y1 - 2009
N2 - Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.
AB - Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.
KW - Lovász-Schrijver operators
KW - stable set problem
KW - semidefinite programming
U2 - 10.1007/s10107-008-0219-8
DO - 10.1007/s10107-008-0219-8
M3 - Journal article
VL - 120
SP - 381
EP - 401
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 2
ER -