Recursive McCormick Linearization of Multilinear Programs

Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLPs). These relaxations can be obtained by using recursive McCormick linearizations (RMLs), by which an MLP is linearized by iteratively substituting bilinear products with artificial variables and constraints. This article introduces a systematic approach to identifying RMLs. We focus on identifying RMLs with a small number of artificial variables and 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 to identify minimum-size RMLs; this problem is NP-hard in general, but we show that it is fixed-parameter tractable if each monomial is composed of at most three variables. Moreover, we explore the structural properties of our formulation to derive an exact MIP model that identifies RMLs of a given size with the best-possible LP relaxation bound. We test our algorithms by conducting numerical experiments on a large collection of MLPs. Numerical results indicate that the RMLs obtained with our algorithms can be significantly smaller than those derived from heuristic or greedy approaches, leading, in many cases, to tighter LP relaxation bounds. Moreover, our linearization strategies can be used to reformulate MLPs as quadratically constrained programs (QCPs), which can then be efficiently solved using state-of-the-art solvers for QCPs. This QCP-based solution approach is highly beneficial for hard MLP instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.