On the facial structure of the set covering polytope
From MaRDI portal
Publication:1122481
DOI10.1007/BF01587087zbMath0675.90059MaRDI QIDQ1122481
Publication date: 1989
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Numerical mathematical programming methods (65K05) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polytopes and polyhedra (52Bxx)
Related Items (43)
The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems ⋮ Knapsack polytopes: a survey ⋮ The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Generalized minor inequalities for the set covering polyhedron related to circulant matrices ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ A polyhedral approach to locating-dominating sets in graphs ⋮ Minor related row family inequalities for the set covering polyhedron of circulant matrices ⋮ On dominating set polyhedra of circular interval graphs ⋮ On the 0,1 facets of the set covering polytope ⋮ A generalization of antiwebs to independence systems and their canonical facets ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Facets and lifting procedures for the set covering polytope ⋮ Integer programming methods for solving binary interdiction games ⋮ Strong formulation for the spot 5 daily photograph scheduling problem ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ The minor inequalities in the description of the set covering polyhedron of circulant matrices ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Transitive packing ⋮ Enhancing an algorithm for set covering problems ⋮ Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks ⋮ On the mixed set covering, packing and partitioning polytope ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ Integer programming approach to static monopolies in graphs ⋮ The anti-join composition and polyhedra ⋮ Lift-and-project ranks of the set covering polytope of circulant matrices ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ Cutting planes in integer and mixed integer programming ⋮ A branch-and-cut algorithm for graph coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Requiring connectivity in the set covering problem ⋮ The nonidealness index of rank-ideal matrices ⋮ On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ How to recycle your facets ⋮ Computational experience with general cutting planes for the set covering problem ⋮ On the structure of linear programs with overlapping cardinality constraints ⋮ Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results ⋮ On the set covering polyhedron of circulant matrices ⋮ On the dominating set polytope of web graphs ⋮ Directed Steiner problems with connectivity constraints ⋮ A parallel genetic algorithm to solve the set-covering problem
Cites Work
- \(K_ i\)-covers. I: Complexity and polytopes
- On certain polytopes associated with graphs
- 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
- Note—A Computational Survey of Methods for the Set Covering Problem
- Faces for a linear inequality in 0–1 variables
- Facets of the Knapsack Polytope From Minimal Covers
- Covering, Packing and Knapsack Problems
- Properties of vertex packing and independence system polyhedra
- On the facial structure of set packing polyhedra
- Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems
- Blocking and anti-blocking pairs of polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the facial structure of the set covering polytope
