Extended formulations for the multilinear polytope of acyclic hypergraphs

2025/01/08 by Del Pia, Alberto, Khajavirad, Aida
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2501.04805

Abstract

This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible region of a linearized binary polynomial optimization problem. By representing the multilinear polytope with hypergraphs, we investigate the connections between hypergraph acyclicity and the complexity of the facial structure of the multilinear polytope. We characterize the acyclic hypergraphs for which a polynomial-size extended formulation for the multilinear polytope can be constructed in polynomial time.

Related

• A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
• The complete edge relaxation for binary polynomial optimization
• The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
• On the complexity of binary polynomial optimization over acyclic hypergraphs
• Simple odd β-cycle inequalities for binary polynomial optimization