Smallest compact formulation for the permutahedron
In this note, we consider the permutahedron, the convex hull of all permutations of \(\{1,2\ldots ,n\}\). We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal AjtaiKomlsSzemerdi sorting network, this extended formulation has \(\varTheta (n\log n)\) variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least \(\varOmega (n \log n)\) inequalities. The results easily extend to the generalized permutahedron.
compact formulations permutahedron extended formulations sorting networks 90c10