Available on ORBi since
05 September 2014
Article (Scientific journals)
The strength of multi-row models
Louveaux, Quentin  ; Poirrier, Laurent; Salvagnin, Domenico
2015 • In Mathematical Programming Computation, 7 (2), p. 113-148
Peer Reviewed verified by ORBi
 

Files


Full Text
fetch-paper.pdf
Author postprint (508.25 kB)

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Mixed-integer programming; Multi-ro cutting planes
Abstract :
[en] We develop a method for computing facet-defining valid inequalities for any mixed-integer set PJ. Our practical implementation does not return only facet- defining inequalities, but it is able to find a separating cut whenever one exists. The separator is not comparable in speed with the specific cutting-plane generators used in branch-and-cut solvers, but it is general-purpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixed- integer problem, even when there exists no specific implementation for computing cuts with PJ. Exploiting this, we evaluate, from a computational perspective, the usefulness of cuts derived from several types of multi-row relaxations. In particular, we present results with four different strengthenings of the two-row intersection cut model, and multi-row models with up to fifteen rows. We conclude that only fully-strengthened two-row cuts seem to offer a significant advantage over two-row intersection cuts. Our results also indicate that the improvement obtained by going from models with very few rows to models with up to fifteen rows may not be worth the increased computing cost.
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;  University of Waterloo > Department of Optimization and Combinatorics
Salvagnin, Domenico;  University of Padova > Department of Information Engineering
Language :
English
Title :
The strength of multi-row models
Publication date :
June 2015
Journal title :
Mathematical Programming Computation
ISSN :
1867-2949
eISSN :
1867-2957
Publisher :
Springer
Volume :
7
Issue :
2
Pages :
113-148
Peer reviewed :
Peer Reviewed verified by ORBi

Statistics


Number of views
120 (11 by ULiège)
Number of downloads
188 (3 by ULiège)

Scopus citations®
 
7
Scopus citations®
without self-citations
4
OpenCitations
 
7

Bibliography


Similar publications



Contact ORBi