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.
By: Sanjeeb Dash, Oktay Günlük, Marco Molinaro
Published in: RC25326 in 2012
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .