On the set covering polytope: Facets with coefficients in {0,1,2,3}

Abstract

Balas and Ng[1,2] characterized the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and gave necessary and sufficient conditions for such an inequality to be facet defining. We extend this study, characterizing the class of valid inequalities with coefficients equal to 0,1,2 or 3, and giving necesary and sufficient conditions for such an inequality to be not dominated, and to be facet defining.Balas and Ng[1,2] characterized the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and gave necessary and sufficient conditions for such an inequality to be facet defining. We extend this study, characterizing the class of valid inequalities with coefficients equal to 0,1,2 or 3, and giving necesary and sufficient conditions for such an inequality to be not dominated, and to be facet defining.