zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On the 0,1 facets of the set covering polytope. (English) Zbl 0675.90054
Necessary and sufficient conditions for an inequality with 0-1 coefficients to define a facet of the set covering polytope associated with the 0-1 constraint matrix A are given. The work is influenced by the results on the set packing problem, where also the notations are defined in the intersection graph of A. For the case that A is a matrix of odd order and the matrix $H<A$ contains exactly two ones per row and per column it is shown how to decide in polynomial time whether $\sum\sp{n}\sb{j=1}x\sb j>(n+1)/2$ is valid. This yields a facet of the set covering polytope.
Reviewer: N.Yanev

90C09Boolean programming
52BxxPolytopes and polyhedra
05C70Factorization, etc.
90C35Programming involving graphs or networks
90C10Integer programming
Full Text: DOI
[1] E. Balas, ”Set covering with cutting planes from conditional bounds,” in: A. Prekopa, ed.,Survey of Mathematical Programming (North-Holland, Amsterdam, 1979) pp. 393--422.
[2] E. Balas, ”Cutting planes from conditional bounds: A new approach to set covering,”Mathematical Programming Study 12 (1980) 19--36. · Zbl 0435.90073
[3] E. Balas and A. C. Ho, ”Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study,”Mathematical Programming Study 12 (1980) 37--60. · Zbl 0435.90074
[4] E. Balas and M. Padberg, ”Set Partitioning: A Survey,”SIAM Review 18 (1976) 710--760. · Zbl 0347.90064 · doi:10.1137/1018115
[5] E. Balas and Shu-Ming Ng, ”Some classes of facets of the set covering polytope,” Research Report, Graduate School of Industrial Administration, Carnegie Mellon University (Pittsburgh, PA, 1984).
[6] E. Balas and Shu-Ming Ng, ”On the set covering polytope: I. All the facets with coefficients in {0, 1, 2},” Research Report MSRR-522, Graduate School of Industrial Administration, Carnegie Mellon University (Pittsburgh, PA, 1986). · Zbl 0674.90079
[7] E. Balas and E. Zemel, ”Critical cutsets of graphs and canonical facets of set-packing polytopes,”Mathematics of Operations Research 2 (1977) 15--19. · Zbl 0447.52010 · doi:10.1287/moor.2.1.15
[8] C. Berge, ”Balanced Matrices,”Mathematical Programming 2 (1972) 19--31. · Zbl 0247.05126 · doi:10.1007/BF01584535
[9] D.C. Cho, M. Padberg and M.R. Rao, ”On the uncapacitated plant location problem. II. Facets and Lifting theorems,”Mathematics of Operations Research 8 (1983) 590--612. · Zbl 0536.90030 · doi:10.1287/moor.8.4.590
[10] V. Chvàtal, ”On certain polytopes associated with graphs,”Journal of Combinatorial Theory B 18 (1975) 138--154. · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[11] M. Conforti, D.G. Corneil and A.R. Mahjoub, ”K i-covers I: Complexity and polytopes,”Discrete Mathematics 58 (1986) 121--142. · Zbl 0584.05052 · doi:10.1016/0012-365X(86)90156-1
[12] G. Cornuéjols and J.M. Thizy, ”Some facets of the simple plant location polytope,”Mathematical Programming 23 (1982) 50--74. · Zbl 0485.90069 · doi:10.1007/BF01583779
[13] D.R. Fulkerson, A.J. Hoffman and R. Oppenheim, ”On balanced matrices,”Mathematical Programming Study 1 (1974) 120--132. · Zbl 0357.90038
[14] J. Hooker, ”Generalized resolution and cutting planes,” Research Report n. MSRR 524, Graduate School of Industrial Administration, Carnegie Mellon University (Pittsburgh, PA, 1986).
[15] M. Laurent, ”A generalization of antiwebs to independence systems and their relation to set covering polytopes,” Technical Report, CNET PAATIM (Issy les Moulineaux, France, 1987).
[16] G.L. Nemhauser and L.E. Trotter, ”Properties of vertex packing and independence system polyhedra,”Mathematical Programming 6 (1974) 48--61. · Zbl 0281.90072 · doi:10.1007/BF01580222
[17] M.W. Padberg, ”On the facial structure of set packing polyhedra,”Mathematical Programming 5 (1973) 199--215. · Zbl 0272.90041 · doi:10.1007/BF01580121
[18] A. Sassano, ”On the facial structure of the set covering polytope,” IASI-CNR Report nr. 132 (Rome, 1985). · Zbl 0675.90059
[19] L.E. Trotter, ”A class of facet producing graphs for vertex packing polyhedra,”Discrete Mathematics 12 (1975) 373--388. · Zbl 0314.05111 · doi:10.1016/0012-365X(75)90077-1
[20] L.A. Wolsey, ”Further facet generating procedures for vertex packing polytopes,”Mathematical Programming 11 (1976) 158--163. · Zbl 0348.90148 · doi:10.1007/BF01580383