In a recent paper, Dash, Dey and Günlük (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied t-branch split cuts for mixed-integer programs for integers t 1. Split cuts are just 1-branch split cuts, and cross cuts are 2-branch split cuts. In this paper, we study whether cross and crooked cross cuts can be separated in an effective manner for practical MIPs, and can yield a non-trivial improvement over the bounds obtained by split cuts. We also study whether such cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by GMI cuts based on single tableau rows. We give positive answers to both these questions for MIPLIB 3.0 problems.
By: Sanjeeb Dash; Oktay Günlük; Juan Pablo Vielma
Published in: RC25176 in 2011
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 .