On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) (Q1121793)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) |
scientific article |
Statements
On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) (English)
0 references
1989
0 references
A class of valid inequalities for the set covering polytope with coefficients 0, 1 or 2 is characterized. Necessary and sufficient conditions for them to be minimal and to be facet defining are given. It is shown that all inequalites in the above class are contained in the elementary closure of the constraints set and \(k=2\) is the largest value of the coefficients in this case. Some conditions for an inequality to cut off a fractional solution of the l.p. relaxation of the set covering problem are also discussed.
0 references
valid inequalities
0 references
set covering polytope
0 references
facet defining
0 references
l.p. relaxation
0 references
0 references
