Research output: Working paper
Research output: Working paper
}
TY - UNPB
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
N1 - This was eventually published as: M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2011) An new approach to the stable set problem based on ellipsoids. In O. Günlük & G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization XV. Lecture Notes in Computer Science, vol. 6655. Heidelberg: Springer.
PY - 2011
Y1 - 2011
N2 - We present a new exact approach to the stable set problem, which avoids the pitfalls of existing approaches based on linear and semidefinite programming. The main idea is to construct an ellipsoid which contains the stable set polytope, in such a way that the upper bound obtained by optimising over the ellipsoid is equal to the Lovasz theta number. This ellipsoid can then be used to construct useful convex programming relaxations of the stable set problem or, more interestingly, to derive cutting planes. These cutting planes turn out to be remarkably strong and easy to generate.
AB - We present a new exact approach to the stable set problem, which avoids the pitfalls of existing approaches based on linear and semidefinite programming. The main idea is to construct an ellipsoid which contains the stable set polytope, in such a way that the upper bound obtained by optimising over the ellipsoid is equal to the Lovasz theta number. This ellipsoid can then be used to construct useful convex programming relaxations of the stable set problem or, more interestingly, to derive cutting planes. These cutting planes turn out to be remarkably strong and easy to generate.
KW - stable set problem
KW - semidefinite programming
KW - convex quadratic programming
KW - cutting planes.
M3 - Working paper
T3 - Management Science Working Paper Series
BT - A new approach to the stable set problem based on ellipsoids
PB - The Department of Management Science
CY - Lancaster University
ER -