Extended Formulations in Combinatorial Optimization
By Volker Kaibel. 2011
192 citations recorded by the source corpus.
The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing attention. In this paper (written for the newsletter Optima of the Mathematical Optimization Society), we provide a brief introduction to this topic and sketch some of the recent developments with respect to both tools for constructing such extended formulations as well as lower bounds on their sizes.
Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering
View Paper: https://www.semanticscholar.org/paper/bc01209403d7a63a03536d76b28aeee0237c3487
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Graphics and Computer-Aided Design
In Industrial and Manufacturing Engineering
Citations in the corpus
- On the Geometric Interpretation of the Nonnegative Rank (2010, background): “, in polynomial-time (see [16] for a survey).”
- Mixed Integer Linear Programming Formulation Techniques (2015, methodology): “For more information on extended formulations in combinatorial optimization we refer the reader to [35, 154, 95] and for more on polyhedral approximations of convex sets we refer the reader to [14, 16, 152] and [93, Chapters 8 and 17].”
- The Why and How of Nonnegative Matrix Factorization (2014, background): “…) = a Ti v j − b i where v j is the j th vertex of P and { x ∈ R n | a Ti x − b i ≥ 0 } its i th facet with a i ∈ R n and b i ∈ R , that is, X is a facet-by-vertex matrix and X ( i, j ) is the slack of the j th vertex with respect to i th facet; see the surveys [30, 69] and the references therein.”