Facet of regular 0-1 polytopes

Abstract

The role of 0-1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. Some connections are established between prime implicants of a monotone or a regular Boolean function β on the one hand, and facets of the convex hull H of the zeros of β on the other. In particular (Corollary 2) a necessary and sufficient condition is given for a constraint of a covering problem to be a facet of the corresponding integer polyhedron. For any prime implicant P of β, a nonempty family F(P) of facets of H is constructed. Proposition 17 gives easy-to-determine sharp upper bounds for the coefficients of these facets when β is regular. A special class of prime implicants is described for regular functions and it is shown that for any P in this class, F(P) consists of one facet of H, and this facet has 0-1 coefficients. Every nontrivial facet of H with 0-1 coefficients is obtained from this class. © 1975 The Mathematical Programming Society.