Reference : An algorithm for the separation of two-row cuts
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/130390
An algorithm for the separation of two-row cuts
English
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Poirrier, Laurent [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore) >]
Feb-2014
Mathematical Programming
Springer
143
1-2
111-146
Yes
International
0025-5610
1436-4646
[en] Integer Programming ; Cutting planes ; Multi-row cuts
[en] We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ) from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.
Researchers
http://hdl.handle.net/2268/130390

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
papierMAPR.pdfAuthor postprint379.21 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.