On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined recently in another paper). We then extend this observation to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables provided that the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one about the equivalence of different definitions of split cuts presented in Cook, Kannan, and Schrijver (1990). This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008). Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded, convex set.

Article

Download

View PDF