  The Binary Polynomial Optimization (BPO) problem is defined as the problem of
maximizing a given polynomial function over all binary points. The main
contribution of this paper is to draw a novel connection between BPO and the
problem of finding the maximal assignment for a Boolean function with weights
on variables. This connection allows us to give a strongly polynomial algorithm
that solves BPO with a hypergraph that is either $\beta$-acyclic or with
bounded incidence treewidth. This result unifies and significantly extends the
known tractable classes of BPO. The generality of our technique allows us to
deal also with extensions of BPO, where we enforce extended cardinality
constraints on the set of binary points, and where we seek $k$ best feasible
solutions. We also extend our results to the significantly more general problem
where variables are replaced by literals. Preliminary computational results
show that the resulting algorithms can be significantly faster than current
state-of-the-art.
