LIFTING FACETS OF ZERO-ONE POLYTOPES

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero-one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero-one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality). © 1978 The Mathematical Programming Society.