Accession Number:

AD1021250

Title:

Stable Sets, Corner Polyhedra and the Chvatal Closure

Descriptive Note:

OSTP Journal Article

Corporate Author:

Carnegie Mellon University Pittsburgh United States

Personal Author(s):

Report Date:

2009-01-01

Pagination or Media Count:

11.0

Abstract:

In this work, we consider a classical 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 in particular that the split closure is not stronger than the Chvatal closure for the stable set problem. The results are obtained via a characterization of the basis and its inverse in terms of a collection of connected components with at most one cycle.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE