Face Lattice Computation Under Symmetry

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. We focus on polytopes arising from combinatorial optimization problems. In particular, we study the metric polytope which is associated with the maxcut and multicommodity flow problems, and to finite metric spaces. We present the orbitwise description of the higher layers of the face lattice of the metric polytope. Based on joint work with Antoine Deza, McMaster University, and Jonathan Li, University of Toronro.