The (not so) trivial lifting in two dimensions

  • When generating cutting-planes for mixed-integer programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure can be computationally costly in practice. For the case of two-row relaxations, we present a practical algorithm that computes trivial lifting coefficients in constant time, for arbitrary maximal lattice-free sets. Computational experiments confirm that the algorithm works well in practice.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ricardo Fukasawa, Laurent Poirrier, Álinson S. Xavier
DOI:https://doi.org/10.1007/s12532-018-0146-5
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2018
Tag:Software; Theoretical Computer Science
Volume:11
Issue:2
Page Number:25
First Page:211
Last Page:235
Mathematical Programming Computation :MPC 2019 - 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.