About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovász–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 Lovász–Schrijver or the Sherali–Adams operator. We also present computational results on the stable set problem with our new operator.