About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.