Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
}
TY - CHAP
T1 - A new approach to the stable set problem based on ellipsoids
AU - Giandomenico, M
AU - Letchford, A N
AU - Rossi, F
AU - Smriglio, S
PY - 2011
Y1 - 2011
N2 - A new exact approach to the stable set problem is presented, which attempts to avoids the pitfalls of existing approaches based on linear and semidefinite programming. The method begins by constructing an ellipsoid that contains the stable set polytope and has the property that the upper bound obtained by optimising over it is equal to the Lovasz theta number. This ellipsoid is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.
AB - A new exact approach to the stable set problem is presented, which attempts to avoids the pitfalls of existing approaches based on linear and semidefinite programming. The method begins by constructing an ellipsoid that contains the stable set polytope and has the property that the upper bound obtained by optimising over it is equal to the Lovasz theta number. This ellipsoid is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.
KW - stable set problem
KW - semidefinite programming
KW - combinatorial optimisation
U2 - 10.1007/978-3-642-20807-2_18
DO - 10.1007/978-3-642-20807-2_18
M3 - Chapter (peer-reviewed)
SN - 9783642208065
T3 - Lecture Notes in Computer Science
SP - 223
EP - 234
BT - Integer Programming and Combinatorial Optimization
A2 - Günlük, Oktay
A2 - Woeginger, Gerhard
PB - Springer
CY - Berlin
T2 - 15th International Conference, IPCO 2011
Y2 - 15 June 2011 through 17 June 2011
ER -