Split Rank of Triangle and Quadrilateral Inequalities

• 成果类型: Article
• 署名作者: Dey, Santanu S.; Louveaux, Quentin
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Liege
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0496
• 发表日期: 2011
• 页码: 432-461
• 关键词: integer; closure; strength; cuts

摘要

A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and Cornuejols and Margot showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. From an example given by Cook et al. it is known that one particular class of facet-defining triangle inequality does not have finite split rank. In this paper we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank.