TY - JOUR

T1 - Sequence independent lifting for mixed integer programs with variable upper bounds

AU - Shebalov, S.

AU - Klabjan, D.

PY - 2006/2/1

Y1 - 2006/2/1

N2 - We investigate the convex hull of the set defined by a single inequality with continuous and binary variables with variable upper bound constraints. We extend the traditional flow cover inequality, and show that it is valid for a restriction of the set in which some variables are fixed. We also give conditions under which this inequality is facet-defining and, when it is not, we show how it can be lifted to obtain valid inequalities for the entire set using sequence independent lifting. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. Finally, we show how these results imply and extend known results about the single node fixed charge flow polyhedron.

AB - We investigate the convex hull of the set defined by a single inequality with continuous and binary variables with variable upper bound constraints. We extend the traditional flow cover inequality, and show that it is valid for a restriction of the set in which some variables are fixed. We also give conditions under which this inequality is facet-defining and, when it is not, we show how it can be lifted to obtain valid inequalities for the entire set using sequence independent lifting. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. Finally, we show how these results imply and extend known results about the single node fixed charge flow polyhedron.

KW - Mixed integer programming

KW - Polyhedral theory

UR - http://www.scopus.com/inward/record.url?scp=29044449426&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=29044449426&partnerID=8YFLogxK

U2 - 10.1007/s10107-005-0664-6

DO - 10.1007/s10107-005-0664-6

M3 - Article

AN - SCOPUS:29044449426

SN - 0025-5610

VL - 105

SP - 523

EP - 561

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2-3

ER -