A Note on Split Rank of Intersection Cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that $\lceil \textrm{log}_2 (l)\rceil$ is a lower bound on the split rank of the intersection cut, where $l$ is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated to obtain a lower bound of $\lceil \textrm{log}_2( n +1) \rceil$ on the split rank of $n$-row mixing inequalities.

Citation

CORE DP 56, 2008

Article

Download

View PDF