The minor inequalities in the description of the set covering polyhedron of circulant matrices
In this work we give a complete description of the set covering polyhedron of circulant matrices <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$C^k_{sk}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msubsup> <mi>C</mi> <mrow> <mi>s</mi> <mi>k</mi> </mrow> <mi>k</mi> </msubsup> </math> </EquationSource> </InlineEquation> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$s=2,3$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>s</mi> <mo>=</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> </mrow> </math> </EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$k \ge 3 $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>k</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math> </EquationSource> </InlineEquation> 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. Copyright Springer-Verlag Berlin Heidelberg 2014
