کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142617 | 957158 | 2011 | 5 صفحه PDF | دانلود رایگان |
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 in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if 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 on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. 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 and convex set.
► We study polyhedral mixed-integer sets with two integer variables.
► We show that all their facet-defining inequalities are crooked cross cuts.
► We extend a characterization of the split closure by Cook, Kannan and Schrijver to crooked cross cuts.
► We show that crooked cross cuts dominate cross cuts or 2-branch split cuts.
► We generalize these results to compact sets defined by convex functions.
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 305–309