  


The Multilinear polytope for acyclic hypergraphs
Alberto Del Pia (delpiawisc.edu) Abstract: 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 mixedinteger 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 Bergeacylic and gammaacyclic hypergraphs. As the Multilinear polytope for gammaacyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomialtime 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 mixedinteger nonlinear optimization problems with multilinear subexpressions. Keywords: Multilinear polytope, Cutting planes, Hypergraph acyclicity, Separation algorithm, Mixedinteger nonlinear optimization Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Global Optimization (Theory ) Citation: manuscript Download: [PDF] Entry Submitted: 09/26/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  