We consider the problem of minimizing a general polynomial of degree d over the integers subject to box-constraints. We propose to underestimate the polynomial objective function by a separable polynomial of degree at most d+1, which is computed by underestimating each monomial independently in the best-possible way, subject to a given touching point. For d <= 4, the local minimizers of the separable underestimator can be computed very quickly by a closed form formula, even in the integer case, while in the case d >= 5 we need numerical methods to minimize the underestimator. We embed the resulting bounds into a branch-and-bound scheme for solving the problem to optimality. Branching consists in splitting up the domain of one of the variables, allowing to compute a tighter separable underestimator given by a new touching point; the latter is chosen as the center of the feasible region. Computationally, our approach compares favorably with various state-of-the-art optimization software, in particular in the sparse case where the number of monomials remains small. This is mostly due to the fast enumeration of the branch-and-bound nodes.