On the composition of convex envelopes for quadrilinear terms
CAFIERI, Sonia
ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien [MAIAA]
See more >
ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien [MAIAA]
CAFIERI, Sonia
ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien [MAIAA]
ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien [MAIAA]
MILLER, Andrew J.
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Chapitre d'ouvrage
This item was published in
Optimization, Simulation, and Control, Optimization, Simulation, and Control. 2013p. pp 1-16
Springer Verlag
English 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. ...Read more >
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 ((x1x2)x3)x4 and (x1x2x3)x4 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.Read less <
English Keywords
quadrilinear
convex relaxation
reformulation
global optimization
spatial branch-and-bound
MINLP
Origin
Hal imported