A Polyhedral Study of Binary Polynomial Programs
A Polyhedral Study of Binary Polynomial Programs
复制标题
DOI：
10.1287/moor.2016.0804
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Alberto Del Pia;Aida Khajavirad
中科院分区：
文献类型：
--
作者：
Alberto Del Pia;Aida Khajavirad
研究了单位超立方体上由多重线性方程组定义的混合整数集的多面体凸船体。𝒮这样的集合经常出现在混合整数非线性优化问题的可因式分解重构中。特别地，集合k表示线性化无约束二元多项式优化问题的可行域。我们定义了一个等价的超图表示的混合整数集的集合，这使我们能够得到几个家庭的方面定义的不等式，结构特性，并提升操作的凸船体在空间中的原始变量。𝒮我们的理论发展扩展了布尔二次多面体和切割多面体文献中的几个著名结果，为设计包含多线性子表达式的非凸问题的新优化算法铺平了道路。
We study the polyhedral convex hull of a mixed-integer set 𝒮 defined by a collection of multilinear equations over the unit hypercube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set 𝒮 represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent hypergraph representation of the mixed-integer set 𝒮, which enables us to derive several families of facet-defining inequalities, structural properties, and lifting operations for its convex hull in the space of the original variables. Our theoretical developments extend several well-known results from the Boolean quadric polytope and the cut polytope literature, paving a way for devising novel optimization algorithms for nonconvex problems containing multilinear sub-expressions.