On the facial structure of the set covering polytope
type: Item
instance of: scholarly article
title: On the facial structure of the set covering polytope
zbMATH Open document ID: 0675.90059
DOI: 10.1007/BF01587087
author: Antonio Sassano
published in: Mathematical Programming. Series A. Series B
publication date: 1989-01-01T00:00:00Z
review text: The set covering problem is the following: \[ \min \{c^ Tx| \quad Ax\geq e_ m,\quad x=(x_ 1,...,x_ n),\quad x_ j\in \{0,1\}\} \] where A is an \(m\times n\) 0-1 matrix, \(c\in R^ n_+\), \(e_ m=(1,...,1)\in R^ M\). The paper examines the structure of the convex hull of feasible solutions of the set covering problem. Using a graph- theoretical equivalent formulation the author gives results concerning the facet-defining inequalities of the above polytope. The method leads to an apparently powerful algorithm for the set covering problem.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4106606
zbMATH Keywords: set covering
zbMATH Keywords: convex hull of feasible solutions
zbMATH Keywords: facet-defining inequalities
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: Cutting planes from conditional bounds: A new approach to set covering
cites work: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
cites work: Facets of the Knapsack Polytope From Minimal Covers
cites work: Note—A Computational Survey of Methods for the Set Covering Problem
cites work: On certain polytopes associated with graphs
cites work: \(K_ i\)-covers. I: Complexity and polytopes
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: Q4124603
cites work: Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems
cites work: Properties of vertex packing and independence system polyhedra
cites work: On the facial structure of set packing polyhedra
cites work: Covering, Packing and Knapsack Problems
cites work: Q4138481
cites work: Q3851094
cites work: Faces for a linear inequality in 0–1 variables
cites work: Lifting the facets of zero–one polytopes
description: scientific article; zbMATH DE number 4106606