On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
From MaRDI portal
Publication:1121793
DOI10.1007/BF01582278zbMath0674.90079OpenAlexW1987163060MaRDI QIDQ1121793
Publication date: 1989
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582278
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09)
Related Items (47)
The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems ⋮ Knapsack polytopes: a survey ⋮ Computational approaches for zero forcing and related problems ⋮ Generalized minor inequalities for the set covering polyhedron related to circulant matrices ⋮ Solving the multi-vehicle multi-covering tour problem ⋮ Solving the asymmetric traveling purchaser problem ⋮ On the 0,1 facets of the set covering polytope ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Facets and lifting procedures for the set covering polytope ⋮ Facetas del politopo de recubrimiento con coeficientes en {0, 1, 2, 3} ⋮ Integer programming methods for solving binary interdiction games ⋮ Strong formulation for the spot 5 daily photograph scheduling problem ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ The Football Pool Polytope ⋮ An integer program for positive semidefinite zero forcing in graphs ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ The Steiner connectivity problem ⋮ The minor inequalities in the description of the set covering polyhedron of circulant matrices ⋮ Transitive packing ⋮ Enhancing an algorithm for set covering problems ⋮ On the mixed set covering, packing and partitioning polytope ⋮ The traveling purchaser problem and its variants ⋮ Polyhedra associated with identifying codes in graphs ⋮ Integer programming approach to static monopolies in graphs ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ The anti-join composition and polyhedra ⋮ Experiments with LAGRASP heuristic for set \(k\)-covering ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Requiring connectivity in the set covering problem ⋮ Set covering approach for reconstruction of sibling relationships ⋮ A flow-based model for the multivehicle covering tour problem with route balancing ⋮ On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ How to recycle your facets ⋮ A comparison of formulations and solution methods for the minimum-envy location problem ⋮ Integer programming models and polyhedral study for the geodesic classification problem on graphs ⋮ Computational experience with general cutting planes for the set covering problem ⋮ Tilted inequalities and facets of the set covering polytope: a theoretical analysis ⋮ Solving the close-enough arc routing problem ⋮ On the structure of linear programs with overlapping cardinality constraints ⋮ Facets for art gallery problems ⋮ Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ Directed Steiner problems with connectivity constraints ⋮ A parallel genetic algorithm to solve the set-covering problem ⋮ Airline crew scheduling: state-of-the-art
Cites Work
- Edmonds polytopes and a hierarchy of combinatorial problems
- Lifting the facets of zero–one polytopes
- Cutting planes from conditional bounds: A new approach to set covering
- Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
- Facet of regular 0–1 polytopes
- Set Partitioning: A survey
- Properties of vertex packing and independence system polyhedra
- On the facial structure of set packing polyhedra
This page was built for publication: On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
