Box-constrained mixed-integer polynomial optimization using separable underestimators

We propose a novel approach to computing lower bounds for box-constrained mixed-integer polynomial minimization problems. Instead of considering convex relaxations, as in most common approaches, we determine a separable underestimator of the polynomial objective function, which can then be minimized easily over the feasible set even without relaxing integrality. The main feature of our approach is the fast computation of a good separable underestimator; this is achieved by computing tight underestimators monomialwise after an appropriate shifting of the entire polynomial. If the total degree of the polynomial objective function is bounded, it suffices to consider finitely many monomials, the optimal underestimators can then be computed offline and hardcoded. For the quartic case, we determine all optimal monomial underestimators analytically. In the case of pure integer problems, we perform an extensive experimental evaluation of our approach. It turns out that the proposed branch-and-bound algorithm clearly outperforms all standard software for mixed-integer optimization when variable domains contain more than two values, while still being competitive in the binary case. Compared to approaches based on linearization, our algorithm suffers significantly less from large numbers of monomials. It could minimize complete random polynomials on ten variables with domain { - 10,10} in less than a minute on average, while no other approach was able to solve any such instance within one hour of running time.