首页 | 本学科首页   官方微博 | 高级检索  
     


A note on the split rank of intersection cuts
Authors:Santanu S. Dey
Affiliation:1.CORE,Université catholique de Louvain,Louvain,Belgium
Abstract: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 élog2 (l)ù{lceil 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 by obtaining a lower bound of élog2( n+1) ù{lceil log_2( n+1) rceil} on the split rank of n-row mixing inequalities.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号