On decomposability of Multilinear sets

We consider the Multilinear set \({\mathcal {S}}\) defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form \(y_I = \prod _{i \in I} x_i\), \(I \in {\mathcal {I}}\), where \({\mathcal {I}}\) denotes a family of subsets of \(\{1,\ldots , n\}\) of 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 when \({\mathcal {S}}\) is decomposable into simpler Multilinear sets \({\mathcal {S}}_j\), \(j \in J\); namely, the convex hull of \({\mathcal {S}}\) can be obtained by convexifying each \({\mathcal {S}}_j\), 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 which \({\mathcal {S}}\) is decomposable into \({\mathcal {S}}_j\), \(j \in J\), 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.