Enumerating Vertices of the Balanced Minimum Evolution Polytope

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however increase exponentially in function of input size. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prüfer coding, we present an iterative enumeration algorithm that is faster than current general purpose softwares and that can be natively massively parallelized.

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however become quickly unpractical. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prfifer coding, we present an iterative enumeration algorithm that is markedly faster than current general purpose softwares and that can be natively massively parallelized. (C) 2019 Elsevier Ltd. All rights reserved.