In this work, we consider a classical formulation of the stable set problem. Wecharacterize its corner polyhedron, i.e. the convex hull of the points satisfying allthe constraints except the non-negativity of the basic variables. We show that thenon-trivial inequalities necessary to describe this polyhedron can be derived fromone row of the simplex tableau as fractional Gomory cuts. It follows in particularthat the split closure is not stronger than the Chvatal closure for the stable setproblem. The results are obtained via a characterization of the basis and its inversein terms of a collection of connected components with at most one cycle.
展开▼
