Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2013 | OriginalPaper | Buchkapitel

On the Composition of Convex Envelopes for Quadrilinear Terms

verfasst von : Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti, Andrew J. Miller

Erschienen in: Optimization, Simulation, and Control

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Within the framework of the spatial Branch-and-Bound algorithm for solving mixed-integer nonlinear programs, different convex relaxations can be obtained for multilinear terms by applying associativity in different ways. The two groupings \((({x}_{1}{x}_{2}){x}_{3}){x}_{4}\) and \(({x}_{1}{x}_{2}{x}_{3}){x}_{4}\) of a quadrilinear term, for example, give rise to two different convex relaxations. In Cafieri et al. (J Global Optim 47:661–685, 2010) we prove that having fewer groupings of longer terms yields tighter convex relaxations. In this chapter we give an alternative proof of the same fact and perform a computational study to assess the impact of the tightened convex relaxation in a spatial Branch-and-Bound setting.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel An Oriented Distance Function Application to Gap Functions for Vector Variational Inequalities
Literatur
1.
C.S. Adjiman, S. Dallwig, C.A. Floudas, and A. Neumaier. A global optimization method, αBB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Computers & Chemical Engineering, 22(9):1137–1158, 1998.
2.
F.A. Al-Khayyal and J.E. Falk. Jointly constrained biconvex programming. Mathematics of Operations Research, 8(2):273–286, 1983.MathSciNetMATHCrossRef
3.
K.M. Anstreicher. Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. Journal of Global Optimization, 43(2-3):471–484, 2009.MathSciNetMATHCrossRef
4.
X. Bao, N.V. Sahinidis, and M. Tawarmalani. Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optimization Methods and Software, 24:485–504, 2009.MathSciNetMATHCrossRef
5.
P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wächter. Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods and Software, 24(4):597–634, 2009.MathSciNetMATHCrossRef
6.
S. Cafieri, J. Lee, and L. Liberti. On convex relaxations of quadrilinear terms. Journal of Global Optimization, 47:661–685, 2010.MathSciNetMATHCrossRef
7.
R.M. Karp and C.H. Papadimitrou. On linear characterizations of combinatorial optimization problems. SIAM Journal on Computing, 11:620–632, 1982.MathSciNetMATHCrossRef
8.
S. Kim and M. Kojima. Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods and Software, 15:201–204, 2001.MathSciNetMATHCrossRef
9.
L. Liberti. Writing global optimization software. In L. Liberti and N. Maculan, editors, Global Optimization: from Theory to Implementation, pages 211–262. Springer, Berlin, 2006.
10.
L. Liberti, S. Cafieri, and F. Tarissan. Reformulations in mathematical programming: a computational approach. In A. Abraham, A.-E. Hassanien, P. Siarry, and A. Engelbrecht, editors, Foundations on Computational Intelligence vol.3, volume 203 of Studies in Computational Intelligence, pages 153–234. Springer, Berlin, 2009.
11.
L. Liberti, C. Lavor, A. Mucherino, and N. Maculan. Molecular distance geometry methods: from continuous to discrete. International Transactions in Operational Research, 18:33–51, 2010.MathSciNetCrossRef
12.
L. Liberti and C.C. Pantelides. Convex envelopes of monomials of odd degree. Journal of Global Optimization, 25:157–168, 2003.MathSciNetMATHCrossRef
13.
L. Liberti, P. Tsiakis, B. Keeping, and C.C. Pantelides. oo \(\mathcal{O}\mathcal{P}\mathcal{S}\). Centre for Process Systems Engineering, Chemical Engineering Department, Imperial College, London, UK, 2001.
14.
15.
J. Luedtke, M. Namazifar, and J. Linderoth. Some results on the strength of relaxations of multilinear functions. Technical Report #1678, University of Wisconsin-Madison. Submitted, 2010.
16.
G.P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems. Mathematical Programming, 10:146–175, 1976.MathSciNetCrossRef
17.
C.A. Meyer and C.A. Floudas. Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes. In C.A. Floudas and P.M. Pardalos, editors, Frontiers in Global Optimization, pages 327–352. Kluwer Academic Publishers, Amsterdam, 2003.
18.
C.A. Meyer and C.A. Floudas. Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. Journal of Global Optimization, 29(2):125–155, 2004.MathSciNetMATHCrossRef
19.
20.
M. Namazifar, P. Belotti, and A.J. Miller. Valid inequalities, separation, and convex hulls for bounded multilinear functions. In preparation. Presented at MIP 2010, Atlanta, USA, 2010.
21.
22.
H.S. Ryoo and N.V. Sahinidis. A branch-and-reduce approach to global optimization. Journal of Global Optimization, 8(2):107–138, March 1996.MathSciNetMATHCrossRef
23.
24.
A. Saxena, P. Bonami, and J. Lee. Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations. Mathematical Programming B, 124:383–411, 2010.MathSciNetMATHCrossRef
25.
A. Saxena, P. Bonami, and J. Lee. Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations. Mathematical Programming, 130(2): 359–413, 2011.MathSciNetMATHCrossRef
26.
H.D. Sherali. Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica, 22:245–270, 1997.MathSciNetMATH
27.
E.M.B. Smith and C.C. Pantelides. A symbolic reformulation/spatial Branch-and-Bound algorithm for the global optimisation of nonconvex MINLPs. Computers & Chemical Engineering, 23:457–478, 1999.CrossRef
28.
F. Tardella. Existence and sum decomposition of vertex polyhedral convex envelopes. Optimization Letters, 2:363–375, 2008.MathSciNetMATHCrossRef
29.
F. Tardella. On the existence of polyhedral convex envelopes. In C.A. Floudas and P.M. Pardalos, editors, Frontiers in Global Optimization, pages 149–188. Kluwer Academic Amsterdam Publishers, Amsterdam, 2008.
30.
M. Tawarmalani and N.V. Sahinidis. Convex extensions and convex envelopes of l.s.c. functions. Mathematical Programming, 93:247–263, 2002.
31.
M. Tawarmalani and N.V. Sahinidis. Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99:563–591, 2004.MathSciNetMATHCrossRef
Metadaten
Titel
On the Composition of Convex Envelopes for Quadrilinear Terms
verfasst von
Pietro Belotti
Sonia Cafieri
Jon Lee
Leo Liberti
Andrew J. Miller
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Optimization, Simulation, and Control

Print ISBN: 978-1-4614-5130-3

Electronic ISBN: 978-1-4614-5131-0

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-5131-0_1