TY - GEN
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
Y1 - 2002
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 - http://www.scopus.com/inward/record.url?scp=84868640825&partnerID=8YFLogxK
U2 - 10.1007/3-540-47867-1_12
DO - 10.1007/3-540-47867-1_12
M3 - Conference contribution
AN - SCOPUS:84868640825
SN - 9783540478676
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 161
EP - 175
BT - Integer Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings
A2 - Cook, William J.
A2 - Schulz, Andreas S.
PB - Springer-Verlag
Y2 - 27 May 2002 through 29 May 2002
ER -