A MODIFIED LIFT-AND-PROJECT PROCEDURE

In recent years the lift-and-project approach has been used successful ly within a branch-and-cut framework to solve large, difficult pure an d mixed 0-1 programs that have resisted solution efforts by pure branc h and bound codes. The approach uses a linear description in a higher dimensional space of the convex hull of the disjunctive set created by imposing one or several 0-1 conditions. By solving a linear program d erived from this higher dimensional representation - the cut generatin g linear program (CGLP) - the standard lift-and-project procedure obta ins a deepest cut in a well defined sense. We propose a modification o f CGLP that allows us to generate not just one deepest cut, but a clas s of cuts with desirable properties, each at the cost of one extra piv ot in the optimal tableau of the modified CGLP (C) 1997 The Mathematic al Programming Society, Inc. Published by Elsevier Science B.V.