TY - GEN
T1 - A framework to derive multidimensional superadditive lifting functions and its applications
AU - Zeng, Bo
AU - Richard, Jean Philippe P.
PY - 2007
Y1 - 2007
N2 - In this paper, we present a systematic method to derive strong superadditive approximations of multidimensional lifting functions using single-dimensional superadditive functions. This constructive approach is based on the observation that, in many cases, the lifting function of a multidimensional problem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.
AB - In this paper, we present a systematic method to derive strong superadditive approximations of multidimensional lifting functions using single-dimensional superadditive functions. This constructive approach is based on the observation that, in many cases, the lifting function of a multidimensional problem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.
UR - http://www.scopus.com/inward/record.url?scp=38049058699&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049058699&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72792-7_17
DO - 10.1007/978-3-540-72792-7_17
M3 - Conference contribution
AN - SCOPUS:38049058699
SN - 9783540727910
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 210
EP - 224
BT - Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
PB - Springer Verlag
T2 - 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
Y2 - 25 June 2007 through 27 June 2007
ER -