Lifted inequalities for 0-1 mixed integer programming: superlinear lifting (Q1424282)

In this paper the authors study the mixed 0-1 knapsack polytope (PS), which is defined by a single knapsack constraint that contains 0-1 and continuous variables. They focus on deriving strong inequalities of PS by sequential lifting of continuous variables fixed at 1 (lifting from 1). Using a former lifting result of their own, they introduce the notion of a superlinear inequality and show that if an inequality is superlinear, then the lifting of continuous variables from 1 is much simpler than in the general case. The superlinearity theory is used next to the lifting of 0-1 cover inequalities to obtain several polynomially computable classes of facets of the mixed 0-1 polytope. The authors show that the superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.