  Linear programming (LP) relaxations are widely employed in exact solution
methods for multilinear programs (MLP). One example is the family of Recursive
McCormick Linearization (RML) strategies, where bilinear products are
substituted for artificial variables, which deliver a relaxation of the
original problem when introduced together with concave and convex envelopes. In
this article, we introduce the first systematic approach for identifying RMLs,
in which we focus on the identification of linear relaxation with a small
number of artificial variables and with strong LP bounds. We present a novel
mechanism for representing all the possible RMLs, which we use to design an
exact mixed-integer programming (MIP) formulation for the identification of
minimum-size RMLs; we show that this problem is NP-hard in general, whereas a
special case is fixed-parameter tractable. Moreover, we explore structural
properties of our formulation to derive an exact MIP model that identifies RMLs
of a given size with the best possible relaxation bound is optimal. Our
numerical results on a collection of benchmarks indicate that our algorithms
outperform the RML strategy implemented in state-of-the-art global optimization
solvers.
