On the Relative Strength of Different Generalizations of Split Cuts

Sanjeeb Dash(sanjeebdus.ibm.com)
Oktay Gunluk(gunlukus.ibm.com)
Marco Molinaro(molinarocmu.edu)

Abstract: 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.

Keywords: integer programming, cutting planes, elementary closures

Category 1: Integer Programming (Cutting Plane Approaches )

Citation: IBM Research Report

Download: [PDF]

Entry Submitted: 11/10/2012
Entry Accepted: 11/11/2012
Entry Last Modified: 11/10/2012

Modify/Update this entry