Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between {\em 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 $\R^2$, 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 {\em 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 {\em crooked cross} cuts. For the two-row continuous group relaxation, we show that {\em 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~\cite{NW90} 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.

Article

Download

View PDF