Facets and lifting procedures for the set covering polytope

• DOI: 10.1007/bf01589100
• Publication Date: 2005-04-28T12:22:34Z
• Authors: Paolo Nobili; Antonio Sassano
• Keywords: Convex polytope; Birkhoff polytope

Given a family of subsetsź of an arbitrary groundsetE, acover ofź is any setC źE having non-empty intersection with every subset inź. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers ofź. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure. Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.