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

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 \in \{0,1\}^{V \cup S}\) $z\in {\{0,1\}}^{V\cup S}$ satisfying a collection of equalities of the form \(z_s = \prod _{v \in s} \sigma _s(z_v)\) $z_s={\prod }_{v\in s}{\sigma }_s(z_v)$ , for all \(s \in S\) $s\in S$ , where \(\sigma _s(z_v) \in \{z_v, 1-z_v\}\) ${\sigma }_s(z_v)\in \{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.