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.
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Balas, Egon; Serra, Thiago: When lift-and-project cuts are different (2020)
- Basu, Amitabh; Sankaranarayanan, Sriram: Can cut-generating functions be good and efficient? (2019)
- Fukasawa, Ricardo; Poirrier, Laurent; Xavier, Álinson S.: The (not so) trivial lifting in two dimensions (2019)
- Fukasawa, Ricardo; Poirrier, Laurent; Xavier, Álinson S.: Intersection cuts for single row corner relaxations (2018)