Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. (English) Zbl 0914.90205

Summary: We present some general as well as explicit characterizations of the convex envelope of multilinear functions defined over a unit hypercube. A new approach is used to derive this characterization via a related convex hull representation obtained by applying the reformulation-linearization technique (RLT) of H. D. Sherali and W. P. Adams [Discrete Appl. Math. 52, No. 1, 83-106 (1994; Zbl 0819.90064)]. For the special cases of multilinear functions having coefficients that are either all \(+1\) or all \(-1\), we develop explicit formulae for the corresponding convex envelopes. Extensions of these results are given for the case when the multilinear function is defined over discrete sets, including explicit formulae for the foregoing special cases when this discrete set is represented by generalized upper bounding (GUB) constraints in binary variables. For more general cases of multilinear functions, we also discuss how this construct can be used to generate suitable relaxations for solving nonconvex optimization problems that include such structures.


90C11 Mixed integer programming
90C09 Boolean programming


Zbl 0819.90064