Uncapacitated flow-based extended formulations
From MaRDI portal
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.
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
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- 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
- 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
(8)- Extended formulations for order polytopes through network flows
- Extended formulations of lower-truncated transversal polymatroids
- Symmetry Matters for Sizes of Extended Formulations
- Extension complexity of formal languages
- Symmetry matters for the sizes of extended formulations
- Extended formulations for radial cones
- Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems
- Cuts over extended formulations by flow discretization
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)
