In a recent paper, Dash, Dey and Gunluk (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.
Article
View Computational Experiments with Cross and Crooked Cross Cuts