The Minor inequalities in the description of the Set Covering Polyhedron of Circulant Matrices

Abstract

In this work we give a complete description of the set covering polyhedron of circulant matrices $C_{sk}^k$ with $s=2,3$ and $k\ge 3$ by linear inequalities. In particular, we prove that every non boolean facet defining inequality is associated with a circulant minor of the matrix. We also give a polynomial time separation algorithm for inequalities involved in the description.

17 pages, 5 figures