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 journalArticle

11 Scopus citations

Abstract

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
Volume98
Issue number1-3
DOIs
StatePublished - Dec 1 2003
Externally publishedYes

Keywords

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

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

  • Cite this