Efficient linear reformulations for binary polynomial optimization problems

We consider unconstrained polynomial minimization problems with binary variables (BPO). These problems can be easily linearized, i.e., reformulated into a MILP in a higher dimensional space. Several linearizations are possible for a given BPO, depending on how each monomial is decomposed and replaced by additional variables and constraints. We focus on finding efficient linearizations that maximize the continuous relaxation bound of the resulting MILP. For this purpose, we introduce the notion of linearization patterns that allow us to model and enumerate the possible decompositions of a degree-d monomial. The assignment of a unique pattern to each monomial of BPO results in a reformulation of BPO into a MILP. Our method, called MaxBound, amounts to searching for an optimal association between monomials and patterns in the sense that it leads to a MILP with the best continuous relaxation bound. We show that this process can be formulated as a MILP which we denote by (MB˜). We further highlight domination properties among the patterns that allow us to discard the dominated patterns and to decrease the size of (MB˜). Another effect of these domination properties is that it now makes sense to search for a reformulation that requires as few additional variables as possible, based only on the non-dominated patterns. We call this reformulation method ND-MinVar and again show that it can be found by solving another MILP. We make an experimental study on degree 4 polynomials that compares the results of both methods and shows the advantages and disadvantages of each.