A new lift-and-project operator

In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a new operator that adds all 0-1 split cuts to the extended formulation. For 0-1 mixed-integer sets with k binary variables, this new operator is guaranteed to obtain the integer hull in k/2 steps compared to k steps for the Lovasz-Schrijver or the Sherali-Adams operator. We also present computational results on the stable set problem with our new operator.

Citation

IBM Research Report

Article

Download

View A new lift-and-project operator