Available on ORBi since
12 September 2012
Article (Scientific journals)
An algorithm for the separation of two-row cuts
Louveaux, Quentin  ; Poirrier, Laurent 
2014 • In Mathematical Programming, 143 (1-2), p. 111-146
Peer Reviewed verified by ORBi
 

Files


Full Text
papierMAPR.pdf
Author postprint (388.31 kB)

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Integer Programming; Cutting planes; Multi-row cuts
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Poirrier, Laurent ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
Language :
English
Title :
An algorithm for the separation of two-row cuts
Publication date :
February 2014
Journal title :
Mathematical Programming
ISSN :
0025-5610
eISSN :
1436-4646
Publisher :
Springer
Volume :
143
Issue :
1-2
Pages :
111-146
Peer reviewed :
Peer Reviewed verified by ORBi

Statistics


Number of views
168 (22 by ULiège)
Number of downloads
229 (12 by ULiège)

Scopus citations®
 
9
Scopus citations®
without self-citations
6

Bibliography


Similar publications



Contact ORBi