POSTPONED

Dr. Allan Sapucaia - CORE

will give a presentation on

Optimizing over path-length matrices of unrooted binary trees

Abstract:

We characterize the set Θn of the path-length matrices induced by unrooted binary trees with n leaves, based in part on a strengthening of results on the tree realization problem. In addition, we present several new valid inequalities and polyhedral results for the convex hull of Θn. We then focus on the Balanced Minimum Evolution Problem (BMEP), a NP-hard nonlinear optimization problem over Θn much studied in the literature on molecular phylogenetics. Working in an extended space, our characterization leads to a first integer linear programming formulation for the BMEP. Modifying this formulation and strengthening the valid inequalities derived earlier by lifting leads to a second formulation which constitutes the core of a branch-and-cut algorithm. Including a new primal heuristic and several separation oracles, this algorithm significantly outperforms the best available exact algorithm for BMEP, based on a dedicated massively parallel branch-and-bound algorithm.