The strength of multi-row models

  • We develop a method for computing facet-defining valid inequalities for any mixed-integer set PJ . While our practical implementation does not return only facet-defining inequalities, 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 presentresults 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 frommodelswith very few rows to models with up to fifteen rows may not be worth the increased computing cost.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Quentin Louveaux, Laurent Poirrier, Domenico Salvagnin
DOI:https://doi.org/10.1007/s12532-014-0076-9
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2014
Tag:Software; Theoretical Computer Science
Volume:7
Issue:2
Page Number:36
First Page:113
Last Page:148
Mathematical Programming Computation :MPC 2015 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.