A generalization of antiwebs to independence systems and their canonical facets

DOI10.1007/BF01589098zbMath0675.90055MaRDI QIDQ1122478

Monique Laurent

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

set coveringknapsackmatroid polytopesantiwebindependence system polytopes

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)

Related Items

Implicit cover inequalities, Knapsack polytopes: a survey, A polyhedral investigation of star colorings, Applying Lehman's theorems to packing problems, Facets and lifting procedures for the set covering polytope, Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model, Strong formulation for the spot 5 daily photograph scheduling problem, Rank inequalities and separation algorithms for packing designs and sparse triple systems., Transitive packing, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph, On the mixed set covering, packing and partitioning polytope, The anti-join composition and polyhedra, Cutting planes in integer and mixed integer programming, Exploring the relationship between max-cut and stable set relaxations, The \(k\)-regular induced subgraph problem, On the structure of linear programs with overlapping cardinality constraints, Minimum partition of an independence system into independent sets, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• A note on node packing polytopes on hypergraphs
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• Matroid Intersection
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• On the Facial Structure of Independence System Polyhedra
• Technical Note—A Note on Zero-One Programming
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• Matroids and the greedy algorithm