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

J. P.P. Richard, I. R. De Farias, G. L. Nemhauser

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)115-143
Number of pages29
JournalMathematical Programming
Issue number1-3
StatePublished - Dec 1 2003
Externally publishedYes


  • 0-1 mixed integer programming
  • Polyhedral theory
  • Superlinear lifting


Dive into the research topics of 'Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting'. Together they form a unique fingerprint.

Cite this