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 UBPP. 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 UBPP from a given quadratization scheme, by associating a new auxiliary variable with each submonomial that appears in the scheme. A quadratic reformulation of UBPP 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 QBP 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 QBP. We consider different types of convexification methods, including complete linearization or quadratic convex reformulations. Theoretical properties of the different phases are recalled from the literature or are further clarified. Finally, we present some experimental results to illustrate the discussion.