Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 28, Issue 2, Pages 1049-1076Publisher
SIAM PUBLICATIONS
DOI: 10.1137/16M1095998
Keywords
multilinear polytope; cutting planes; hypergraph acyclicity; separation algorithm; mixed-integer nonlinear optimization
Categories
Funding
- National Science Foundation [CMMI-1634768]
Ask authors/readers for more resources
We consider the multilinear polytope defined as the convex hull of the set of binary points z satisfying a collection of equations of the form z(e) = Pi(zv)(v is an element of e), e is an element of E, where E denotes a family of subsets of {1, . . . , n} of cardinality at least two. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as 0 - 1 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 0 - 1 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 subexpressions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available