On decomposability of Multilinear sets
On decomposability of Multilinear sets
复制标题
DOI：
10.1007/s10107-017-1158-z
复制
发表时间：
2017-05
影响因子：
2.7
通讯作者：
Alberto Del Pia;Aida Khajavirad
中科院分区：
文献类型：
--
作者：
Alberto Del Pia;Aida Khajavirad
我们认为多线性集定义为二元点（x，y）的集合满足形式为的多线性方程组，其中表示基数至少为2的子集族。这样的集合出现在许多类型的非凸优化问题的可因式分解重构中，包括二元多项式优化。当可分解为更简单的多线性集时，研究多线性集的凸船体的表面结构就可能得到极大的简化，也就是说，通过分别对每个多线性集进行凸化，就可以得到多线性集的凸船体。本文研究了多重线性集的可分解性。利用多线性集的一种等价超图表示，基于两两交超图的结构，得到了多线性集可分解为，的充要条件.我们的刻画统一和推广了现有的布尔二次多面体的可分解性结果。最后，我们提出了一个多项式时间的算法，以最佳地将多线性集分解成更简单的子集。我们提出的算法可以很容易地纳入分支和切割为基础的全球解决方案作为预处理步骤切割生成。
We consider the Multilinear setdefined as the set of binary points (x,y) satisfying a collection of multilinear equations of the form,, wheredenotes a family of subsets ofof cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible whenis decomposable into simpler Multilinear sets,; namely, the convex hull ofcan be obtained by convexifying each, separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under whichis decomposable into,, based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.