Polyhedra Computation Under Symmetry

Abstract

<p>The last 15 years have seen 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 metric polytope associated to the well-known maxcut and multicommodity flow problems, as well as to finite metric spaces. To tackle the huge size of the problem hundreds of trillions of vertices - a parallel or bitwise enumeration algorithm was implemented and run on Shared Hierarchical Academic Research Computing Network (SHARCNET) clusters. Exploiting the high degree of symmetry, we provide for t he first time a description of the highly degenerate metric polytope in dimension 36. The description consists of 1 056 368 orbits and is conjectured to be complete. While the validity of the dominating set conjecture [Laurent-Poljak, 1992] is proven for the overwhelming majority of the known vertices of the metric polytope, we disprove the conjecture by exhibiting counterexamples in dimensions 36 and 45.</p>