标题： 一种关于二元多项式优化的知识编译方法 显示英文标题

标题： A Knowledge Compilation Take on Binary Polynomial Optimization

摘要： 二元多项式优化（BPO）问题被定义为在一个所有二元点上最大化给定多项式函数的问题。 本文的主要贡献在于建立了BPO与知识编译领域之间的一种新的联系。 这种联系使我们能够统一并显著扩展BPO的最先进方法，无论是在可处理类方面，还是在存在扩展公式方面。 特别是，对于具有超图的BPO实例，这些超图要么是$\beta$-无环的，要么具有有界的入射树宽，我们为BPO获得了强多项式算法，并为相应的多线性多胞形获得了多项式大小的扩展公式。 我们的技术的普适性使我们能够为BPO的扩展形式获得相同类型的结果，在这些扩展形式中，我们在二元点集上强制执行扩展的基数约束，并且变量被替换为文字。 我们还为上述问题的变体获得了强多项式算法，在该变体中，我们寻求$k$个最佳可行解，而不仅仅是单一最优解。 计算结果显示，由此产生的算法可以比当前最先进的算法显著更快。 显示英文摘要

摘要： 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 field of Knowledge Compilation. This connection allows us to unify and significantly extend the state-of-the-art for BPO, both in terms of tractable classes, and in terms of existence of extended formulations. In particular, for instances of BPO with hypergraphs that are either $\beta$-acyclic or with bounded incidence treewidth, we obtain strongly polynomial algorithms for BPO, and extended formulations of polynomial size for the corresponding multilinear polytopes. The generality of our technique allows us to obtain the same type of results for extensions of BPO, where we enforce extended cardinality constraints on the set of binary points, and where variables are replaced by literals. We also obtain strongly polynomial algorithms for the variant of the above problems where we seek $k$ best feasible solutions, instead of only one optimal solution. Computational results show that the resulting algorithms can be significantly faster than current state-of-the-art.