Stable Sets, Corner Polyhedra and the Chvatal Closure

Abstract

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 Chvatal closure for the edge relaxation of the stable set problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2009
Accession Number
AD1021088

Entities

People

  • Gérard Cornuéjols
  • Manoel Campelo

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Coefficients
  • Commerce
  • Equations
  • Inclusions
  • Inequalities
  • Integrals
  • Literature
  • Mathematics
  • Optimization
  • Schools
  • Sequences
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research