A Knowledge Compilation Take on Binary Polynomial Optimization

In Binary Polynomial Optimization (BPO), the goal is to find a binary point maximizing a given polynomial function. In this paper, we establish a novel connection between BPO and restricted Boolean circuits from the field of knowledge compilation, enabling us to both unify and significantly extend the state-of-the-art for BPO. Leveraging this connection, we identify a new tractable class of BPO instances: those whose associated hypergraphs have bounded incidence treewidth. This is a significantly broader structural condition than the previously studied bounded primal treewidth, as it allows polynomials of high degree while still exploiting the underlying hypergraph structure. For this class, we obtain a strongly polynomial-time algorithm and a polynomial-size extended formulation for the corresponding multilinear polytope. Our approach also recovers known tractability results for BPO with \(\beta \) $\beta$ -acyclic hypergraphs and extends naturally to BPO variants with cardinality constraints, with variables replaced by literals, and to the problem of finding the top-k feasible solutions. Preliminary computational experiments indicate that the resulting algorithms can significantly outperform current state-of-the-art methods.