A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
成果类型：
Article
署名作者：
Del Pia, Alberto; Khajavirad, Aida
署名单位：
University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02009-4
发表日期：
2024
页码：
269-301
关键词：
摘要：
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 (upsilon is an element of e) z(upsilon) for all e is an element of E. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of ss-acyclic hypergraphs, hence characterizing the acyclic hypergraphs for which such a formulation can be constructed.
来源URL：