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 formu- lations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutation of variables. Such a permutation-invariance structure naturally implies a quadratic-sized extended formulation for the envelopes through the use of disjunctive programming. The opti- mization and separation problems are answered directly without using this extension. The problem symmetry also implies that permuting the coefficients of a core set of facets generates all the facets. We provide some necessary conditions for a valid inequality to be a core facet. These conditions are applied to obtain envelopes for two classes, sym- metric supermodular functions and multilinear monomials with reflection symmetry, thereby yielding alternate proofs to literature. Furthermore, we use constructs from the reformulation-linearization-technique to completely characterize the points lying on each facet.
Original language | English |
---|
Publisher | Optimization Online |
---|
Number of pages | 37 |
---|
Publication status | Published - 12 Oct 2020 |
---|