TY - JOUR
T1 - Lifted inequalities for 0-1 mixed integer programming
T2 - Superlinear lifting
AU - Richard, J. P.P.
AU - De Farias, I. R.
AU - Nemhauser, G. L.
PY - 2003
Y1 - 2003
N2 - We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds.We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.
AB - We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds.We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.
KW - 0-1 mixed integer programming
KW - Polyhedral theory
KW - Superlinear lifting
UR - http://www.scopus.com/inward/record.url?scp=29044445395&partnerID=8YFLogxK
U2 - 10.1007/s10107-003-0399-1
DO - 10.1007/s10107-003-0399-1
M3 - Article
AN - SCOPUS:29044445395
VL - 98
SP - 115
EP - 143
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-3
ER -