A Massively Parallel Branch-&-Bound Algorithm for the Balanced Minimum Evolution Problem

The Balanced Minimum Evolution Problem (BMEP) is an APX}-hard network design problem that consists of finding a phylogeny that minimizes the cross-entropy of the molecular sequences extracted from a given set of taxa. By combining massive parallelism with recent theoretical advances on the polyhedral combinatorics of the problem and new insights on the relationships between the BMEP and information entropy, we design a new exact solution algorithm that proves to be up to an order of magnitude faster than the current state-of-the-art sequential-version on generic instances and able to solve up to 25% more taxa within the same time limit. We also investigate some issues related to numerical stability and statistical consistency of the BMEP, arising in particular when dealing with large instances. We show, as a negative finding, that no rescaling technique may ensure numerical stability, by guaranteeing at the same time the statistical consistency of the optimal solution to the problem.