On the facial structure of the set covering polytope (Q1122481): Difference between revisions

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.