Article (Scientific journals)
Split rank of triangle and quadrilateral inequalities
Dey, Santanu; Louveaux, Quentin
2011In Mathematics of Operations Research, 36 (3), p. 432-461
Peer Reviewed verified by ORBi
 

Files


Full Text
coredp2009_55.pdf
Publisher postprint (625.49 kB)
Download
Annexes
aussois09ql.pdf
Publisher postprint (696.79 kB)
Slides of a talk held in Aussois (January 2009)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Mixed-integer programming; Two rows; Split rank
Abstract :
[en] 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. 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. Through a result by Cook et al., 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.
Disciplines :
Mathematics
Author, co-author :
Dey, Santanu;  Université Catholique de Louvain - UCL > Center for Operations Research and Econometrics
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Optimisation discrète
Language :
English
Title :
Split rank of triangle and quadrilateral inequalities
Publication date :
August 2011
Journal title :
Mathematics of Operations Research
ISSN :
0364-765X
eISSN :
1526-5471
Publisher :
Institute for Operations Research (INFORMS)
Volume :
36
Issue :
3
Pages :
432-461
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 09 January 2010

Statistics


Number of views
141 (21 by ULiège)
Number of downloads
152 (5 by ULiège)

Scopus citations®
 
14
Scopus citations®
without self-citations
10
OpenCitations
 
14

Bibliography


Similar publications



Contact ORBi