We prove that there are 0 1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X 0,1 ^n such that conv(X) must have extension complexity at least 2^ n 2 * (1-o(1)) . In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not contained in P_ poly , our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.
A formulation of size @math for the permutahedron was provided by Goemans @cite_15 . In fact, @cite_15 also showed that this is tight up to constant factors. The lower bound of @cite_15 is based on the insight that the number of facets of any extension must be at least logarithmic in the number of vertices of the target polytope (which is @math for the permutahedron). The perfect matching polytope for planar graphs and graphs with bounded genus does admit a compact formulation @cite_14 @cite_5 . A useful tool to design such formulations is the Theorem of Balas @cite_9 @cite_10 , which describes the convex hull of the union of polyhedra. For @math -hard problems, one can of course not expect the existence of any compact formulation. Nevertheless, Bienstock @cite_21 gave an approximate formulation of size @math for the Knapsack polytope. This means, optimizing any linear function over the approximate polytope will give the optimum Knapsack value, up to a @math factor. For a more detailed literature review, we refer to the surveys of Conforti, Cornu jols and Zambelli @cite_11 and of Kaibel @cite_1 .
@cite_14 @cite_9 @cite_21 @cite_1 @cite_5 @cite_15 @cite_10 @cite_11
2068066892 2337855014 2280546767 2952253187
In this note, we consider the permutahedron, the convex hull of all permutations of @math 1,2?,n . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai---Komlos---Szemeredi sorting network, this extended formulation has @math ?(nlogn) 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 @math Ω(nlogn) inequalities. The results easily extend to the generalized permutahedron. This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. The Birkhoff polytope (the convex hull of the set of permutation matrices) is frequently invoked in formulating relaxations of optimization problems over permutations. The Birkhoff polytope is represented using @math variables and constraints, significantly more than the @math variables one could use to represent a permutation as a vector. Using a recent construction of Goemans (2010), we show that when optimizing over the convex hull of the permutation vectors (the permutahedron), we can reduce the number of variables and constraints to @math in theory and @math in practice. We modify the recent convex formulation of the 2-SUM problem introduced by (2013) to use this polytope, and demonstrate how we can attain results of similar quality in significantly less computational time for large @math . To our knowledge, this is the first usage of Goemans' compact formulation of the permutahedron in a convex optimization problem. We also introduce a simpler regularization scheme for this convex formulation of the 2-SUM problem that yields good empirical results. We prove that there are 0 1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X 0,1 ^n such that conv(X) must have extension complexity at least 2^ n 2 * (1-o(1)) . In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not contained in P_ poly , our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.