On the 0,1 facets of the set covering polytope (Q1122477)

Necessary and sufficient conditions for an inequality with 0-1 coefficients to define a facet of the set covering polytope associated with the 0-1 constraint matrix A are given. The work is influenced by the results on the set packing problem, where also the notations are defined in the intersection graph of A. For the case that A is a matrix of odd order and the matrix \(H<A\) contains exactly two ones per row and per column it is shown how to decide in polynomial time whether \(\sum^{n}_{j=1}x_ j>(n+1)/2\) is valid. This yields a facet of the set covering polytope.