A framework to derive multidimensional superadditive lifting functions and its applications

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
PublisherSpringer Verlag
Pages210-224
Number of pages15
ISBN (Print)9783540727910
DOIs
StatePublished - 2007
Externally publishedYes
Event12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, United States
Duration: Jun 25 2007Jun 27 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4513 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
CountryUnited States
CityIthaca, NY
Period6/25/076/27/07

Fingerprint Dive into the research topics of 'A framework to derive multidimensional superadditive lifting functions and its applications'. Together they form a unique fingerprint.

  • Cite this

    Zeng, B., & Richard, J. P. P. (2007). A framework to derive multidimensional superadditive lifting functions and its applications. In Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings (pp. 210-224). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4513 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72792-7_17