Reference : Split rank of triange and quadrilateral inequalities
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
Split rank of triange and quadrilateral inequalities
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
13th combinatorial optimization workshop
January 2009
[en] Mixed-integer programming ; Cutting planes
[en] 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, Kannan and Schrijver it is known that one particular class of facet-defining triangle inequality does not have finite split rank. In this talk we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank.

File(s) associated to this reference

Fulltext file(s):

Open access
aussois09ql.pdfAuthor preprint680.46 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.