Optimization Online


Split Rank of Triangle and Quadrilateral Inequalities

Santanu Dey(santanu.dey***at***uclouvain.be)
Quentin Louveaux(q.louveaux***at***ulg.ac.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 non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2007) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. Through a result by Cook et al. (1990), it is known that one particular class of facet-defining triangle inequality does not have a finite split rank. In this paper, we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank. The proof is constructive and given a facet-defining 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 )


Download: [PDF]

Entry Submitted: 06/04/2009
Entry Accepted: 06/04/2009
Entry Last Modified: 06/04/2009

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