Reference : Split rank of triangle and quadrilateral inequalities
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/35086
Split rank of triangle and quadrilateral inequalities
English
Dey, Santanu [Université Catholique de Louvain - UCL > Center for Operations Research and Econometrics > > >]
Louveaux, Quentin mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Optimisation discrète >]
Aug-2011
Mathematics of Operations Research
Institute for Operations Research (INFORMS)
36
3
432-461
Yes (verified by ORBi)
International
0364-765X
1526-5471
[en] Mixed-integer programming ; Two rows ; Split rank
[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.
http://hdl.handle.net/2268/35086
10.1287/moor.1110.0496

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
coredp2009_55.pdfNo commentaryPublisher postprint610.83 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
aussois09ql.pdfSlides of a talk held in Aussois (January 2009)680.46 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.