期刊
SIAM JOURNAL ON OPTIMIZATION
卷 28, 期 2, 页码 1049-1076出版社
SIAM PUBLICATIONS
DOI: 10.1137/16M1095998
关键词
multilinear polytope; cutting planes; hypergraph acyclicity; separation algorithm; mixed-integer nonlinear optimization
资金
- National Science Foundation [CMMI-1634768]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据