  


On Polytopes with Linear Rank with respect to Generalizations of the Split Closure
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: In this paper we study the rank of polytopes contained in the 01 cube with respect to $t$branch split cuts and $t$dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$dimensional 01 cube, the work of Balas implies that the split rank can be at most $n$, and this bound is tight as Cornu\'ejols and Li gave an example with split rank $n$. All known examples with high split rank  i.e., at least $cn$ for some positive constant $c < 1$  are defined by exponentially many (as a function of $n$) linear inequalities. For any fixed integer $t > 0$, we give a family of polytopes contained in $[0,1]^n$ for sufficiently large $n$ such that each polytope has empty integer hull, is defined by $O(n)$ inequalities, and has rank $\Omega(n)$ with respect to $t$dimensional lattice cuts. Therefore the split rank of these polytopes is $\Omega(n)$. It was shown earlier that there exist generalized branchandbound proofs, with logarithmic depth, of the nonexistence of integer points in these polytopes. Therefore, our lower bound results on split rank show an exponential separation between the depth of branchandbound proofs and split rank. Keywords: cutting planes, integer programming, split rank, split cut, split closure Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Combinatorial Optimization (Polyhedra ) Citation: Download: [PDF] Entry Submitted: 10/08/2021 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  