Advances on the polyhedral study of Set Covering problems

The Set Cover problem consists in, given a collection C of subsets of a finite set S and integer k, determine if there is a subset U ⊆ C such that |U| ≤ k and every element of S belongs to at least one member of U. We study the set covering polytopes, which are defined by the convex hull of characteristic vectors of solutions to Set Cover. Set covering problems are related to structures called clutters. Clutters are collections of minimal subsets of a set. This work also extends the study of 𝒩-set inequalities, which are a generalization of rank inequalities. We define two classes of inequalities to covering problems and provide sufficient conditions for them to be facet-defining. The facet-defining inequalities and lifting procedures for set covering polytopes introduced in this work can be readily extended to other set covering problems.