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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references