科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 left perpendicular k/2 right perpendicular 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.
- 出版日期2017-3-1
- 单位IBM
