A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs

Abstract

We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs, hence characterizing the acyclic hypergraphs for which such a formulation can be constructed.