Uncapacitated flow-based extended formulations (Q745688)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Uncapacitated flow-based extended formulations |
scientific article |
Statements
Uncapacitated flow-based extended formulations (English)
0 references
14 October 2015
0 references
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.
0 references
special polytopes
0 references
linear programming
0 references
combinatorial optimization
0 references
programming involving graphs and networks
0 references
0 references
0 references
0 references