The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02122-y
• 发表日期: 2025
• 页码: 717-761
• 关键词: Acyclicity; bounds

摘要

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the set of binary points z is an element of {0, 1}(V boolean OR S) satisfying a collection of equalities of the form z(s) = Pi(v is an element of s) sigma(s)(z(v)), for all s is an element of S, where sigma(s) (z(v)) is an element of {z(v), 1 - z(v)}, and where S is a multiset of subsets of V. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.