In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. 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 this set is decomposable into simpler sets. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation, we derive necessary and sufficient conditions under which the Multilinear set is decomposable into simpler sets, 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.
Citation
Submitted manuscript