A Massively Parallel Exact Solution Algorithm for the Balanced Minimum Evolution Problem

Daniele Catanzaro, Martin Frohn and Raffaele Pesenti
Additional contact information
Daniele Catanzaro: Université catholique de Louvain, LIDAM/CORE, Belgium
Martin Frohn: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2021023, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The Balanced Minimum Evolution Problem (BMEP) is an [APX]-hard nonlinear 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.

Keywords: Combinatorial optimization; network design; balanced minimum evolution; implicit enumeration algorithms; parallel computing; numerical stability (search for similar items in EconPapers)
Pages: 41
Date: 2021-01-01
New Economics Papers: this item is included in nep-cmp and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2021023

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().