A note on the split rank of intersection cuts

• 成果类型: Article
• 署名作者: Dey, Santanu S.
• 署名单位: Universite Catholique Louvain
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0329-y
• 发表日期: 2011
• 页码: 107-124
• 关键词: mixed-integer programs; cutting planes; gomory cuts; closure; inequalities; polyhedra; progress

摘要

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 [log(2)(l)] 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 by obtaining a lower bound of [log2(n + 1)] on the split rank of n-row mixing inequalities.