Reference : Split rank of triangle and quadrilateral inequalities
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Split rank of triangle and quadrilateral inequalities
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 >]
Mathematics of Operations Research
Institute for Operations Research (INFORMS)
Yes (verified by ORBi)
[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.

File(s) associated to this reference

Fulltext file(s):

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.