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

Jean Philippe P. Richard; Ismael R. De Farias; George L. Nemhauser

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

Jean Philippe P. Richard
, Ismael R. De Farias
, George L. Nemhauser

Research output: Contribution to journal › Conference article › peer-review

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. We introduce the concept of superlinear inequalities and show that our lifting scheme can be significantly simplified for them. Finally, we show that superlinearity results can be generalized to nonsuperlinear inequalities when the coefficients of the continuous variables lifted are large.

Original language	English (US)
Pages (from-to)	161-175
Number of pages	15
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2337 LNCS
State	Published - Dec 1 2002
Externally published	Yes
Event	9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States Duration: May 27 2002 → May 29 2002

Find It

Find It at U of M Libraries

Cite this

Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms. / Richard, Jean Philippe P.; De Farias, Ismael R.; Nemhauser, George L.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2337 LNCS, 01.12.2002, p. 161-175.

Research output: Contribution to journal › Conference article › peer-review

@article{0cbed71263e34b169d8bffed3192575b,

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. We introduce the concept of superlinear inequalities and show that our lifting scheme can be significantly simplified for them. Finally, we show that superlinearity results can be generalized to nonsuperlinear inequalities when the coefficients of the continuous variables lifted are large.",

author = "Richard, \{Jean Philippe P.\} and \{De Farias\}, \{Ismael R.\} and Nemhauser, \{George L.\}",

year = "2002",

month = dec,

day = "1",

language = "English (US)",

volume = "2337 LNCS",

pages = "161--175",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 ; Conference date: 27-05-2002 Through 29-05-2002",

}

TY - JOUR

T1 - Lifted inequalities for 0-1 mixed integer programming

T2 - 9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002

AU - Richard, Jean Philippe P.

AU - De Farias, Ismael R.

AU - Nemhauser, George L.

PY - 2002/12/1

Y1 - 2002/12/1

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. We introduce the concept of superlinear inequalities and show that our lifting scheme can be significantly simplified for them. Finally, we show that superlinearity results can be generalized to nonsuperlinear inequalities when the coefficients of the continuous variables lifted are large.

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. We introduce the concept of superlinear inequalities and show that our lifting scheme can be significantly simplified for them. Finally, we show that superlinearity results can be generalized to nonsuperlinear inequalities when the coefficients of the continuous variables lifted are large.

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

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

M3 - Conference article

AN - SCOPUS:84868640825

SN - 0302-9743

VL - 2337 LNCS

SP - 161

EP - 175

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Y2 - 27 May 2002 through 29 May 2002

ER -

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

Abstract

Find It

Other files and links

Fingerprint

Cite this