Carnegie Mellon University
Stable Sets Corner Polyhedra and the Chv\xe1tal Closure.pdf.pdf' (130.31 kB)
Download file

Stable Sets, Corner Polyhedra and the Chvátal Closure

Download (130.31 kB)
journal contribution
posted on 1981-09-16, 00:00 authored by Manoel Campêlo, Gerard CornuejolsGerard Cornuejols
We consider the edge formulation of the stable set problem. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived from one row of the simplex tableau as fractional Gomory cuts. It follows that the split closure is not stronger than the Chvátal closure for the edge relaxation of the stable set problem.




Usage metrics