Quadratization and convexification in polynomial binary optimization

In this paper, we discuss several reformulations and solution approaches for the problem of minimizing a polynomial in binary variables (P). We review and integrate different literature streams to describe a methodology consisting of three distinct phases, together with several possible variants for each phase. The first phase determines a recursive decomposition of each monomial of interest into pairs of submonomials, down to the initial variables. The decomposition gives rise to a so-called quadratization scheme. The second phase builds a quadratic reformulation of (P) from a given quadratization scheme, by associating a new auxiliary variable with each submonomial that appears in the scheme. A quadratic reformulation of (P) is obtained by enforcing relations between the auxiliary variables and the monomials that they represent, either through linear constraints or through penalty terms in the objective function. The resulting quadratic problem (QP) is non-convex in general and is still difficult to solve. At this stage we introduce the third phase of the resolution process, which consists in convexifying (QP). We consider different types of convexification methods, including complete linearization or quadratic convex reformulations. Mathematical properties of the different phases are formally established and some relations between them are clarified. Finally, we present some experimental results which illustrate the discussion and which support the practical relevance of quadratic reformulation methods.