Uncapacitated flow-based extended formulations (Q745688)

This paper is on extended formulations of a polytope \(P\) which is a linear description of \(P\) in an extended space. \(P\) can be considered as the projection of the polyhedron of the extension. Extended formulations are of interest because every optimization problem on \(P\) can also be defined over an extension of \(P\) and the number of constraints might be substantially smaller. If the size of an extension is its number of facets, then size lower bounding techniques are increasingly important. The authors study so-called flow based extended formulations of all flows in uncapacitated networks. They prove size lower bounds for flow based extensions of the perfect matching polytope of the complete bipartite graph with \(2n\) vertices and the traveling salesman polytope on the complete graph with \(n\) vertices.