Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and basic relaxations. We present a complete containment relationship between the closures of split, rank 2 split, cross, crooked cross and general multi-branch split cuts. More specifically, we show that 3-branch split cuts strictly dominate crooked cross cuts, which in turn strictly dominate cross cuts. We also show that multi-branch split cuts are incomparable to rank 2 split cuts. In addition, we also show that cross cuts, and hence crooked cross cuts, cannot always be obtained from 2-row relaxations or from basic relaxations. Together, these results settle some open questions raised in earlier papers.
Citation
IBM Research Report