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 $$C^k_{sk}$$ C s k k with $$s=2,3$$ s = 2 , 3 and $$k \ge 3 $$ k ≥ 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. Copyright Springer-Verlag Berlin Heidelberg 2014

MoreLess

Year of publication:	2014
Authors:	Bianchi, Silvia ; Nasini, Graciela ; Tolomei, Paola
Published in:	Computational Statistics. - Springer. - Vol. 79.2014, 1, p. 69-85
Publisher:	Springer
Subject:	Polyhedral combinatorics \| Set covering \| Circulant matrices

More details

Extent:	text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010847992