A note on the split rank of intersection cuts (Q647399): Difference between revisions

The author analyzes mixed integer programs with \(m\) integer variables, \(n\) nonnegative continuous variables and a restriction vector \(f\) with at least one non-integer component. In a branch-and-cut framework split cuts -- introduced by Egon Balas more than 35 years ago by using disjunctions for integer-valued inequalities -- have shown to be of certain value; by adding all possible split cuts to the linear programming relaxation \(M\) one gets the first split closure \(M^1\), which was shown to be a polyhedron. Applying the split closure procedure to the resulting set iteratively again yields the second split closure \(M^2,\dots,M^t,\dots\) The split rank of a valid inequality for the convex hull of the mixed integer set of solutions is defined as the smallest integer \(t\) , such that the inequality is valid for \(M^t\) (or can be infinite shown by simple examples where the facet-defining inequality cannot be obtained using split cuts). This rank indicates how difficult it is to obtain an inequality using split cuts. The main result of the paper shows a lower bound on the split rank of the class of intersection cuts (a general class due to Balas too): after having constructed a polyhedral subset of the lattice-free convex set \(P\), which contains the vector \(f\) in its interior, one looks for a number \(k\) of integer points that lie on different faces of \(P\); then \(\log_2 (k)\) is a lower bound for the rank. This result can be specialized for \(n\)-row mixing inequalities yielding a lower bound of \(\log_2(n+1)\). The proofs are based mainly on geometric arguments.