Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0675.90054
Cornuéjols, Gérard; Sassano, Antonio
On the 0,1 facets of the set covering polytope.
(English)
[J] Math. Program., Ser. A 43, No.1, 45-55 (1989). ISSN 0025-5610; ISSN 1436-4646/e

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.
[N.Yanev]
MSC 2000:
*90C09 Boolean programming
52Bxx Polytopes and polyhedra
05C70 Factorization, etc.
90C35 Network programming
90C10 Integer programming

Keywords: facet; set covering polytope; set packing; intersection graph

Highlights
Master Server