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

2023/09/15 by Del Pia, Alberto, Khajavirad, Aida · 2 citations
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2309.08693

Abstract

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary points satisfying a collection of equations containing pseudo-Boolean functions. 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.

Cited by

• Projection-width: a unifying structural parameter for separable discrete optimization
• A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization

Related

• Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
• Extended formulations for the multilinear polytope of acyclic hypergraphs
• The complete edge relaxation for binary polynomial optimization
• A Knowledge Compilation Take on Binary Polynomial Optimization
• Relaxations for binary polynomial optimization via signed certificates