On the composition of convex envelopes for quadrilinear terms

Pietro Belotti (1) , Sonia Cafieri (2) , Jon Lee (3) , Leo Liberti (4) , Andrew J. Miller (5, 6)

1 Department of Mathematical Sciences [Clemson]
2 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
3 Department of Mathematical Sciences, TJ Watson
4 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
5 IMB - Institut de Mathématiques de Bordeaux
6 Realopt - Reformulations based algorithms for Combinatorial Optimization

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.

Mots clés: quadrilinear; convex relaxation; reformulation; global optimization; spatial branch-and-bound; MINLP

Domaines: Recherche opérationnelle [math.OC]

Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti, Andrew J. Miller. On the composition of convex envelopes for quadrilinear terms. Optimization, Simulation, and Control, Springer Verlag, pp 1-16, 2013, Springer Optimization and Its Applications, Volume 76, 978-1-4614-5130-3. ⟨10.1007/978-1-4614-5131-0_1⟩. ⟨hal-00769671⟩