  


A Note on Split Rank of Intersection Cuts
Santanu Dey (santanu.deyuclouvain.be) 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 latticefree convex set that is used to generate the intersection cut is constructed. We call this subset the restricted latticefree 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 latticefree set satisfying the condition that no two points lie on the same facet of the restricted latticefree 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. Keywords: Split Rank , Intersection Cuts, Mixing Inequalities, Constant Capacity LotSizing Problem Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: CORE DP 56, 2008 Download: [PDF] Entry Submitted: 09/22/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  