The minor inequalities in the description of the set covering polyhedron of circulant matrices

Silvia Bianchi (), Graciela Nasini () and Paola Tolomei ()

Mathematical Methods of Operations Research, 2014, vol. 79, issue 1, 69-85

Abstract: 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

Keywords: Polyhedral combinatorics; Set covering; Circulant matrices (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-013-0453-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:79:y:2014:i:1:p:69-85

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-013-0453-6

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().