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.

By: Merve Bodur, Sanjeeb Dash, Oktay Günlük

Published in: European Journal of Operational Research, volume 257, (no 2), pages 420-8 in 2017

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .