A framework to derive multidimensional superadditive lifting functions and its applications

Bo Zeng; Jean Philippe P. Richard

doi:10.1007/978-3-540-72792-7_17

A framework to derive multidimensional superadditive lifting functions and its applications

Bo Zeng, Jean Philippe P. Richard

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
Publisher	Springer Verlag
Pages	210-224
Number of pages	15
ISBN (Print)	9783540727910
DOIs	https://doi.org/10.1007/978-3-540-72792-7_17
State	Published - 2007
Externally published	Yes
Event	12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, United States Duration: Jun 25 2007 → Jun 27 2007

Publication series

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

Other

Other	12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
Country	United States
City	Ithaca, NY
Period	6/25/07 → 6/27/07

Access

10.1007/978-3-540-72792-7_17

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

A framework to derive multidimensional superadditive lifting functions and its applications. / Zeng, Bo; Richard, Jean Philippe P.

Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings. Springer Verlag, 2007. p. 210-224 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4513 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Zeng, B & Richard, JPP 2007, A framework to derive multidimensional superadditive lifting functions and its applications. in Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4513 LNCS, Springer Verlag, pp. 210-224, 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII, Ithaca, NY, United States, 6/25/07. https://doi.org/10.1007/978-3-540-72792-7_17

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

Zeng, Bo ; Richard, Jean Philippe P. / A framework to derive multidimensional superadditive lifting functions and its applications. Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings. Springer Verlag, 2007. pp. 210-224 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9c62d4ba02ac4fb399c52b088ed162cf,

title = "A framework to derive multidimensional superadditive lifting functions and its applications",

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

author = "Bo Zeng and Richard, {Jean Philippe P.}",

year = "2007",

doi = "10.1007/978-3-540-72792-7_17",

language = "English (US)",

isbn = "9783540727910",

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

publisher = "Springer Verlag",

pages = "210--224",

booktitle = "Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings",

note = "12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII ; Conference date: 25-06-2007 Through 27-06-2007",

}

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 -