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

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

doi:10.1007/s10107-003-0398-2

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 journal › Article › peer-review

27 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 language	English (US)
Pages (from-to)	89-113
Number of pages	25
Journal	Mathematical Programming
Volume	98
Issue number	1-3
DOIs	https://doi.org/10.1007/s10107-003-0398-2
State	Published - 2003
Externally published	Yes

Keywords

0-1 mixed integer programming
Lifting
Polyhedral theory

Publisher link

10.1007/s10107-003-0398-2

Find It

Find It at U of M Libraries

Cite this

@article{87ed6cfb4a4a40fda5f9c2a3f1911d17,

title = "Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms",

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.",

keywords = "0-1 mixed integer programming, Lifting, Polyhedral theory",

author = "Richard, \{J. P.P.\} and \{De Farias\}, \{I. R.\} and Nemhauser, \{G. L.\}",

year = "2003",

doi = "10.1007/s10107-003-0398-2",

language = "English (US)",

volume = "98",

pages = "89--113",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - Lifted inequalities for 0-1 mixed integer programming

T2 - Basic theory and algorithms

AU - Richard, J. P.P.

AU - De Farias, I. R.

AU - Nemhauser, G. L.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - 0-1 mixed integer programming

KW - Lifting

KW - Polyhedral theory

UR - https://www.scopus.com/pages/publications/25444499490

UR - https://www.scopus.com/pages/publications/25444499490#tab=citedBy

U2 - 10.1007/s10107-003-0398-2

DO - 10.1007/s10107-003-0398-2

M3 - Article

AN - SCOPUS:25444499490

SN - 0025-5610

VL - 98

SP - 89

EP - 113

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-3

ER -

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

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this