Spring 2021

The Multilinear Polytope for Acyclic Hypergraphs

Tuesday, May 11th, 2021 8:30 am10:30 am

Add to Calendar


Aida Khajavirad (Lehigh University)

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 derive  explicit characterizations for the multilinear polytope of Berge-acylic and gamma-acyclic hypergraphs and present polynomial-time algorithms for the corresponding optimization problems. As an important byproduct, we present a new class of cutting planes for constructing stronger polyhedral relaxations of mixed-integer nonlinear optimization problems with multilinear sub-expressions. Finally, we detail the complexity of corresponding separation problems and embed the proposed cut generation algorithm at every node of the branch-and-reduce global solver BARON. Extensive computational results will be presented.