Split Rank of Triangle and Quadrilateral Inequalities

Split Rank of Triangle and Quadrilateral Inequalities

0.00 Avg rating0 Votes
Article ID: iaor20118535
Volume: 36
Issue: 3
Start Page Number: 432
End Page Number: 461
Publication Date: Aug 2011
Journal: Mathematics of Operations Research
Authors: ,
Keywords: relaxation methods
Abstract:

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 Cornuéjols 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.

Reviews

Required fields are marked *. Your email address will not be published.