Unpublished conference/Abstract (Scientific congresses and symposiums)
Split rank of triange and quadrilateral inequalities
Louveaux, Quentin
200913th combinatorial optimization workshop
 

Files


Full Text
aussois09ql.pdf
Author preprint (696.79 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Mixed-integer programming; Cutting planes
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
Split rank of triange and quadrilateral inequalities
Publication date :
January 2009
Event name :
13th combinatorial optimization workshop
Event place :
Aussois, France
Event date :
January 2009
By request :
Yes
Available on ORBi :
since 21 May 2012

Statistics


Number of views
49 (0 by ULiège)
Number of downloads
38 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi