首页 | 本学科首页   官方微博 | 高级检索  
     


Stable sets, corner polyhedra and the Chvátal closure
Authors:Manoel Campê  lo,Gé  rard Cornué  jols
Affiliation:a Departamento de Estatística e Matemática Aplicada, Universidade Federal do Ceará, Brazil
b Tepper School of Business, Carnegie Mellon University, Pitsburgh, PA 15213, United States
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 Chvátal closure for the edge relaxation of the stable set problem.
Keywords:Stable set   Corner polyhedron   Chvá  tal closure   Odd cycle inequality
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号