Face Lattice Computation under Symmetry

Abstract

The last 15 years have seen a significant progress in the development of general purpose algorithms and software for polyhedral computation. Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general purpose algorithms. They are, however, highly structured and attention has turned to exploiting this structure, particularly symmetry. We focus on polytopes arising from combinatorial optimization problems. In particular, we study the face lattice of the metric polytope associated with the well-known maxcut and multicommodity flow problems, as well as with finite metric spaces. Exploiting the high degree of symmetry, we provide the first complete orbitwise description of the higher layers of the face lattice of the metric polytope for any dimension. Further computational and combinatorial issues are presented.