Thursday, 13:45 - 14:10 h, Room: H 0104


Fabrizio Rossi
A branch-and-cut for the stable set problem based on an ellipsoidal relaxation

Coauthors: Monia Giandomenico, Adam N. Letchford, Stefano Smriglio


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ász 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 ellipsoid 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.


Talk 2 of the invited session Thu.2.H 0104
"Strong relaxations for stable set and lot sizing" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  loans online . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.