Reference : Split rank of triange and quadrilateral inequalities

	Document type :	Scientific congresses and symposiums : Unpublished conference
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/2268/122926

Title :	Split rank of triange and quadrilateral inequalities
Language :	English
Author, co-author :	Louveaux, Quentin [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Publication date :	Jan-2009
Peer reviewed :	No
On invitation :	Yes
Event name :	13th combinatorial optimization workshop
Event date :	January 2009
Event place (city) :	Aussois
Event country :	France
Keywords :	[en] 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.
Permalink :	http://hdl.handle.net/2268/122926
Other URL :	http://www.iwr.uni-heidelberg.de/groups/comopt/conferences/aussois2009/index.html

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access aussois09ql.pdf Author preprint 680.46 kB View/Open

All documents in ORBi are protected by a user license.

 

© ULg Library Network |  Feedback |  ORBi legal notices

Dspace v1.5