Uncapacitated flow-based extended formulations

DOI10.1007/S10107-015-0862-9MaRDI QIDQ745688zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Kanstantsin Pashkovich

Publication date 14 October 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3119

zbMATH Keywords

combinatorial optimizationlinear programmingprogramming involving graphs and networksspecial polytopes

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds on the sizes of extended formulations. Network flows are a central paradigm in discrete optimization, and are widely used to design extended formulations. We prove exponential lower bounds on the sizes of uncapacitated flow-based extended formulations of several polytopes, such as the (bipartite and non-bipartite) perfect matching polytope and TSP polytope. We also give new examples of flow-based extended formulations, e.g., for 0/1-polytopes defined from regular languages. Finally, we state a few open problems.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1063799
• Bounds for global optimization of capacity expansion and flow assignment problems
• Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
• A simplex method for uncapacitated pure-supply infinite network flow problems
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• Solving to optimality the uncapacitated fixed-charge network flow problem
• Capacitated Confluent Flows: Complexity and Algorithms
• On formulations of the stochastic uncapacitated lot-sizing problem
• A computational comparison of flow formulations for the capacitated location-routing problem

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An algebraic approach to symmetric extended formulations
• An information complexity approach to extended formulations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Combinatorial bounds on nonnegative rank and extended formulations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Common information and unique disjointness
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
• scientific article; zbMATH DE number 5485464 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Integrality gaps for Sherali-Adams relaxations
• Lectures on Polytopes
• Linear programming relaxations of \textsc{maxcut}
• Linear vs. semidefinite extended formulations
• Maximum matching and a polyhedron with 0,1-vertices
• Network flows. Theory, algorithms, and applications.
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Polyhedral combinatorics and combinatorial optimization
• Polyhedral proof methods in combinatorial optimization
• Rank bounds and integrality gaps for cutting planes procedures
• Symmetry matters for the sizes of extended formulations
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(9)

• Extended formulations for order polytopes through network flows
• Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems
• Extended formulations for radial cones
• Cuts over extended formulations by flow discretization
• Symmetry matters for the sizes of extended formulations
• Symmetry Matters for Sizes of Extended Formulations
• Extended formulations of lower-truncated transversal polymatroids
• Extended formulations for control languages defined by finite-state automata
• Extension complexity of formal languages

This page was built for publication: Uncapacitated flow-based extended formulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745688)