Lifted inequalities for 0–1 mixed integer programming: Superlinear lifting

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.