Optimization Online


A Note on Split Rank of Intersection Cuts

Santanu Dey (santanu.dey***at***uclouvain.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 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.

Keywords: Split Rank , Intersection Cuts, Mixing Inequalities, Constant Capacity Lot-Sizing 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
Entry Accepted: 09/22/2008
Entry Last Modified: 10/09/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society