On decomposability of Multilinear sets

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1158-z
• 发表日期: 2018
• 页码: 387-415
• 关键词: constrained quadratic programs; clique separators; relaxations; graphs; DECOMPOSITION; nonconvex; polytope

摘要

We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of 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 is decomposable into simpler Multilinear sets , ; namely, the convex hull of can 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 which is 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.