Strength of facets for the set covering and set packing polyhedra on circulant matrices.

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; MONTELAR, MARÍA SUSANA

Gramado

Simposio; LAGOS 09- V Latin American Algorithms, Graphs and Optimization Symposium; 2009

In this paper we prove that the N+-rank coincides with the disjunctive and N-rankfor the linear relaxation of the set covering polyhedron of the circulant matricesC^k_{sk+1} and C^k_{sk} if s ≥ k + 1. We analyze the behavior of the same operators onthe clique relaxation of the stable set polytope of W^2_n with n ≥ 6, which has beencompletely described by Dahl. We define the strength of the facets with respectto the linear relaxation of the set packing and set covering polyhedra, according tothese operators and compare the results with Goemans? measure.