Publication
EJOR
Paper

A new lift-and-project operator

View publication

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.

Date

01 Mar 2017

Publication

EJOR

Authors

Share