On mixed-integer sets with two integer variables |
| |
Authors: | Sanjeeb Dash,Santanu S. Dey,Oktay Gü nlü k |
| |
Affiliation: | aIBM Research, United States;bGeorgia Inst. Tech., United States |
| |
Abstract: | 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. |
| |
Keywords: | Cutting planes Split cuts Crooked cross cuts Mixed-integer programming |
本文献已被 ScienceDirect 等数据库收录! |