On the Face Lattice of the Metric Polytope

In this paper we study enumeration problems for polytopes arising from combinatorial optimization problems. While these polytopes turn out to be quickly intractable for enumeration algorithms designed for general polytopes, algorithms using their large symmetry groups can exhibit strong performances. Specifically we consider the metric polytope mn on n nodes and prove that for n≥ 9 the faces of codimension 3 of mn are partitioned into 15 orbits …