Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

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

Research output: Contribution to journalArticlepeer-review

26 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. We develop a lifting theory for the continuous variables. In particular, we present a pseudo-polynomial algorithm for the sequential lifting of the continuous variables and we discuss its practical use.

Original languageEnglish (US)
Pages (from-to)89-113
Number of pages25
JournalMathematical Programming
Volume98
Issue number1-3
DOIs
StatePublished - 2003
Externally publishedYes

Keywords

  • 0-1 mixed integer programming
  • Lifting
  • Polyhedral theory

Fingerprint

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

Cite this