The minor inequality facet conjecture for circulant set covering polyhedra

About 14 years old · traced to

Let CnkC_n^k be a circulant matrix, let W⊂ZnW\subset\mathbb Z_n define a relevant circulant minor isomorphic to Cn′k′C_{n'}^{k'}, and let Q(Cnk)Q(C_n^k) denote the associated set covering polyhedron. The corresponding minor inequality is

∑i∈W2xi+∑i∉Wxi≥⌈n′k′⌉.\sum_{i\in W}2x_i+\sum_{i\notin W}x_i\geq\left\lceil\frac{n'}{k'}\right\rceil.

Here, WW is relevant when n′≠0(modk′)n'\neq0\pmod {k'} and ⌈n′/k′⌉>⌈n/k⌉\left\lceil n'/k'\right\rceil>\left\lceil n/k\right\rceil. The minor inequality facet conjecture. A relevant minor inequality corresponding to a minor of CnkC_n^k isomorphic to Cn′k′C_{n'}^{k'} defines a facet of Q(Cnk)Q(C_n^k) if and only if n′=1(modk′)n'=1\pmod {k'}. The conjecture seeks a complete characterization of when these non-boolean, non-rank inequalities are facet defining; the supplied source gives no evidence of resolution.

References

Primary source

Silvia M. Bianchi, Graciela L. Nasini and Paola B. Tolomei, “The Minor inequalities in the description of the Set Covering Polyhedron of Circulant Matrices”, arXiv:1206.1300 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.