Some results on the strength of relaxations of multilinear functions (Q1925788)

Global optimization problems containing multilinear functions are considered. The relationship between the convex hull relaxation and the McCormic relaxation is studied. For a special case of only bilinear terms, the bounds are provided for how much the McCormic relaxation can be worse than concave and convex envelopes. The obtained results can be useful for the construction of branch and bound type algorithms, especially for the problems where the associated graph is dense. Numerical examples are provided to illustrate the properties of the considered relaxations.