Generating Facets for the Independence System Polytope
Fouilhoux, Pierre; Labbé, Martine; Mahjoub, Ali Ridha; Yaman, Hande (2009), Generating Facets for the Independence System Polytope, SIAM Journal on Discrete Mathematics, 23, 3, p. 1484-1506. http://dx.doi.org/10.1137/070695988
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Discrete Mathematics
MetadataShow full item record
Abstract (EN)In this paper, we present procedures to obtain facet-defining inequalities for the independence system polytope. These procedures are defined for inequalities which are not necessarily rank inequalities. We illustrate the use of these procedures by deriving strong valid inequalities for the acyclic induced subgraph, triangle free induced subgraph, bipartite induced subgraph, and knapsack polytopes. Finally, we derive a new family of facet-defining inequalities for the independence system polytope by adding a set of edges to antiwebs.
Subjects / Keywordsinteger programming; polyhedral combinatorics; independence system polytope; lifting; nonrank facets
Showing items related by title and author.
The Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié