On the Skeleton of the Metric Polytope

We consider convex polyhedra with applications to well-known combinatorial optimization problems: the metric polytope mn and its relatives. For n ≤ 6 the description of the metric polytope is easy as mn has at most 544 vertices partitioned into 3 orbits; m7 - the largest previously known instance - has 275 840 vertices but only 13 orbits. Using its large symmetry group, we enumerate orbitwise 1 550 825 600 vertices of the 28-dimensional metric …