A New Lift-and-Project Operator

In this paper, we analyze the strength of split cuts in a lift-and-project framework. We observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific elementary split cuts to appropriate extended formulations and demonstrate how to strengthen these hierarchies using additional split cuts. We define a new operator by adding all split cuts from 0-1 split disjunctions on binary variables and show that this operation is significantly stronger than the original procedure. For 0-1 mixed-integer sets with k binary variables, the new operator is guaranteed to obtain the integer hull in [k=2] steps compared to k steps for the Lovasz and Schrijver operator. We also present computational results on the stable set problem with our new operator.