Valid Inequalities and Convex Hulls for Multilinear Functions - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Electronic Notes in Discrete Mathematics Year : 2010

Valid Inequalities and Convex Hulls for Multilinear Functions

Abstract

We study the convex hull of the bounded, nonconvex set of a product of n variables for any n ≥ 2. We seek to derive strong valid linear inequalities for this set, which we call M_n; this is motivated by the fact that many exact solvers for nonconvex problems use polyhedral relaxations so as to compute a lower bound via linear programming solvers. We present a class of linear inequalities that, together with the well-known McCormick inequalities, defines the convex hull of M_2. This class of inequalities, which we call lifted tangent inequalities, is uncountably infinite, which is not surprising given that the convex hull of M_n is not a polyhedron. This class of inequalities generalizes directly to M_n for n > 2, allowing us to define strengthened relaxations for these higher dimensional sets as well.

Dates and versions

hal-00547924 , version 1 (17-12-2010)

Identifiers

Cite

Pietro Belotti, Andrew J. Miller, Mahdi Namazifar. Valid Inequalities and Convex Hulls for Multilinear Functions. Electronic Notes in Discrete Mathematics, 2010, 36, pp.805-812. ⟨10.1016/j.endm.2010.05.102⟩. ⟨hal-00547924⟩
98 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More