Optimization Online


The (not so) Trivial Lifting in Two Dimensions

Ricardo Fukasawa(rfukasawa***at***uwaterloo.ca)
Laurent Poirrier(lpoirrier***at***uwaterloo.ca)
Alinson Xavier(axavier***at***uwaterloo.ca)

Abstract: 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: lifting, cutting-planes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 11/02/2016
Entry Accepted: 11/02/2016
Entry Last Modified: 11/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society