On the set covering polyhedron of circulant matrices

A well known family of minimally nonideal matrices is the family of the incidence matrices of chordless odd cycles. A natural generalization of these matrices is given by the family of circulant matrices. Ideal and minimally nonideal circulant matrices have been completely identified by Cornuejols and Novick [G. Cornuejols. B. Novick, Ideal 0 - 1 matrices, Journal of Combinatorial Theory B 60 (1994) 145-157]. In this work we classify circulant matrices and their blockers in terms of the inequalities involved ill their set covering polyhedra. We exploit the results due to Cornuejols and Novick in the above-cited reference for describing the set covering polyhedron of blockers of circulant matrices. Finally, we point out that the results found on circulant matrices and their blockers present a remarkable analogy with a similar analysis of webs and antiwebs due to Pecher and Wagler [A. Pecher, A. Wagler. A construction for non-rank facets of stable set polytopes of webs, European Journal of Combinatorics 27 (2006) 1172-1185; A. Pecher, A. Wagler, Almost all webs are not rank-perfect, Mathematical Programming Series B 105 (2006) 311-328] and Wagler [A. Wagler, Relaxing perfectness: Which graphs are 'Almost' perfect?, in: A Groetschel (Ed.), The Sharpest Cut, Impact of Manfred Padberg and his work, in: SIAM/MPS Series on Optimization, vol. 4, Philadelphia, 2004; A.Wagler, Antiwebs are rank-perfect, 4OR 2 (2004) 149-152]. (C) 2008 Elsevier B.V. All rights reserved.