Optimizing over Path-Length Matrices of Unrooted Binary Trees

Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order $n\geq 3$ must satisfy to encode the PLM of a UBT with $n$ leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set $\T$ of PLMs induced by the set of UBTs with $n$ leaves. We also identify key polyhedral results as well as facet-defining and valid inequalities for the convex hull of these matrices. We then examine how these results can be used to develop a new Branch-\&-Cut algorithm for the Balanced Minimum Evolution Problem (BMEP), a $\mathcal{NP}$-hard nonlinear optimization problem over $\T$ much studied in the literature on molecular phylogenetics. We present a new valid integer linear programming formulation for this problem and we show how to refine it, by removing redundant variables and constraints. We also show how to strengthen the reduced formulation by including lifted versions of the previously identified facet-defining and valid inequalities. We provide separation oracles for these inequalities and we exploit the tight lower bound provided by the linear programming relaxation of this formulation to design a new primal heuristic for the BMEP. The results of extensive computational experiments show that the Branch-&-Cut algorithm derived from this study outperforms the current state-of-the-art exact solution algorithm for the problem.