  


Split Rank of Triangle and Quadrilateral Inequalities
Santanu Dey(santanu.deyuclouvain.be) Abstract: A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and nonnegative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2007) showed that the facetdefining inequalities of this set are either split cuts or intersection cuts obtained from latticefree triangles and quadrilaterals. Through a result by Cook et al. (1990), it is known that one particular class of facetdefining triangle inequality does not have a finite split rank. In this paper, we show that all other facetdefining triangle and quadrilateral inequalities have finite split rank. The proof is constructive and given a facetdefining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it. Keywords: Mixed Integer Programming, Cutting Planes, Split Rank Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 06/04/2009 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  