Two-Dimensional Lattice-Free Cuts and Asymmetric Disjunctions for Mixed-Integer Polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in R2, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than triangles with one integer point in the relative interior of each side. We also show that all 2D lattice-free cuts are crooked cross cuts, and that some cutting planes in the literature for variants of the two-row continuous group relaxation are crooked cross cuts. For general mixed integer sets, we extend results in Nemhauser and Wolsey [24] on the equivalence of split cuts and mixed-integer rounding cuts. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.