A Knowledge Compilation Take on Binary Polynomial Optimization

• 成果类型: Article; Early Access
• 署名作者: Capelli, Florent; Del Pia, Alberto; Di Gregorio, Silvia
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite d'Artois; CNRS - Institute for Information Sciences & Technologies (INS2I); University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02375-9
• 发表日期: 2026-06-10
• 关键词: binary polynomial optimization; Knowledge Compilation; BOOLEAN FUNCTIONS; strongly polynomial algorithms; extended formulations; algorithm; SEQUENCES

摘要

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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}-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.