 Facets and Rank of Integer PolyhedraManfred W. Padberg
A chapter in Facets of Combinatorial Optimization, 2013, pp 23-58 from Springer Abstract: Abstract We discuss several methods of determining all facets of “small” polytopes and polyhedra and give several criteria for classifying the facets into different facet types, so as to bring order into the multitude of facets as, e.g., produced by the application of the double description algorithm (DDA). Among the forms that we consider are the normal, irreducible and minimum support representations of facets. We study symmetries of vertex and edge figures under permissible permutations that leave the underlying polyhedron unchanged with the aim of reducing the numerical effort to find all facets efficiently. Then we introduce a new notion of the rank of facets and integer polyhedra. In the last section, we present old and new results on the facets of the symmetric traveling salesman polytope $\mathcal{Q}_{T}^{n}$ with up to n=10 cities based on our computer calculations and state a conjecture that, in the notion of rank ρ(P) introduced here, asserts $\rho(\mathcal{Q}_{T}^{n}) = n - 5$ for all n≥5. This conjecture is supported by our calculations up to n=9 and, possibly, n=10. Keywords: Extreme Point; Nonnegativity Constraint; Facet Type; Linear Description; Vertex Class (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_2 Ordering information: This item can be ordered from DOI: 10.1007/978-3-642-38189-8_2 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.