A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

The authors develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, they begin with a class of product-form facets that subsume Padberg’s clique, cut, and generalized cut inequality facets. By applying the proposed general approach to this class of facets, the authors derive a specially structured polyhedron whose vertices describe all facets that are simultaneous liftings, of these facets. They identify specific classes of vertices for this polyhedron to reveal a new class of facets for the quadric polytope. Such an approach can be applied to lifting other facets, as well as to analyze other combinatorial optimization problems.