  


The Multilinear polytope for gammaacyclic hypergraphs
Alberto Del Pia (delpiawisc.edu) Abstract: In this paper, 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 highly efficient polynomial algorithm to solve the separation problem. Our results imply polynomial solvability of the corresponding classes of binary polynomial optimization problems and provide new types of cutting planes for a variety of mixedinteger nonlinear optimization problems. Keywords: Multilinear polytope, Hypergraph acyclicity, Separation algorithm, Cutting planes, Mixed integer 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  