Optimization Online


On the Relative Strength of Different Generalizations of Split Cuts

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Marco Molinaro (molinaro***at***cmu.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: 03/02/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society