A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS

We propose a cutting plane algorithm for mixed 0-1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through th e solution of a linear program that has about twice the size of the us ual LP relaxation. A lifting step is used to reduce the size of the LP 's needed to generate the cuts. An additional strengthening step sugge sted by Balas and Jeroslow is then applied. We report our computationa l experience with a preliminary version of the algorithm. This approac h is related to the work of Balas on disjunctive programming, the matr ix cone relaxations of Lovasz and Schrijver and the hierarchy of relax ations of Sherali and Adams.