A Geometric Perspective on Lifting

Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to lift these inequalities for integral nonbasic variables by considering maximal lattice-free convex set...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2011-05, Vol.59 (3), p.569-577
Main Authors: Conforti, Michele, Cornuéjols, Gérard, Zambelli, Giacomo
Format: Article
Language:English
Subjects:
Analysis
Applied sciences
Convex analysis
Exact sciences and technology
Geometric planes
Integer programming
Integers
Lattice theory
Linear programming
Management science
Mathematical functions
Mathematical inequalities
Mathematical programming
Mathematical vectors
Methods
Operational research and scientific management
Operational research. Management science
Polyhedrons
Polytopes
programming/integer/cutting plane
Series, Geometric
Studies
Tableaux
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to lift these inequalities for integral nonbasic variables by considering maximal lattice-free convex sets in a higher dimensional space. We apply this approach to several examples. In particular, we identify cases in which the lifting is unique.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.1110.0916