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

M. Sánchez-García, M.I. Sobrón, B. Vitoriano

Annals of Operations Research Vol. 81, pp. 343 - 356

Summary:

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.

Keywords: Set covering, facets, polyhedral combinatorics, combinatorial optimization

JCR Impact Factor and WoS quartile: 4,800 - Q1 (2022)

DOI reference: https://doi.org/10.1023/A:1018969410431

Published on paper: June 1998.

Citation:
M. Sánchez-García, M.I. Sobrón, B. Vitoriano, On the set covering polytope: Facets with coefficients in {0,1,2,3}. Annals of Operations Research. Vol. 81, pp. 343 - 356, June 1998.