We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the Multilinear polytope in conjunction with the acyclicity degree of the underlying hypergraph. We provide explicit characterizations of the Multilinear polytopes corresponding to Berge-acylic and gamma-acyclic hypergraphs. As the Multilinear polytope for gamma-acyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomial-time algorithm to solve the separation problem, implying polynomial solvability of the corresponding class of binary polynomial optimization problems. As an important byproduct, we present a new class of cutting planes for constructing tighter polyhedral relaxations of mixed-integer nonlinear optimization problems with multilinear sub-expressions.
Citation
manuscript