论文标题
对称多线性多项式在框约束上的多面体分析
Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints
论文作者
论文摘要
众所周知，多线性多项式在盒子上的凸和凹形包膜是多面体函数。这些信封的指数尺寸扩展和投影配方也已知。我们考虑了相对于变量排列的多项式多项式的凸化问题。这种置换不变的结构自然意味着通过使用析取编程的二次尺寸扩展配方，用于信封。在不使用此扩展的情况下，直接回答了优化和分离问题。问题对称性允许在不使用任何扩展的情况下直接回答优化和分离问题。这也意味着将核心方面的系数置换为生成所有方面。我们提供一些必要的条件和一些足够的条件，使有效的不平等成为核心方面。这些条件应用于获得两个类别的信封：对称超模块函数和具有反射对称性的多线性单元，从而为文献提供了其他证据。此外，我们使用重新构造线性化技术中的构造来完全表征每个方面上的一组点。
It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized extended formulation for the envelopes through the use of disjunctive programming. The optimization and separation problems are answered directly without using this extension. The problem symmetry allows the optimization and separation problems to be answered directly without using any extension. It also implies that permuting the coefficients of a core set of facets generates all the facets. We provide some necessary conditions and some sufficient conditions for a valid inequality to be a core facet. These conditions are applied to obtain envelopes for two classes: symmetric supermodular functions and multilinear monomials with reflection symmetry, thereby yielding alternate proofs to the literature. Furthermore, we use constructs from the reformulation-linearization-technique to completely characterize the set of points lying on each facet.
