Abstract

Path-Length Matrices (PLMs) form a prominent tree encoding scheme often employed in optimization problems defined over Unrooted Binary Trees (UBTs), i.e., trees having $n \ge 3$ leaves and internal nodes with degree three. Characterizing the properties that an integer matrix of order $n$ must possess to encode the PLM of a UBT eluded for decades the efforts of the scientific community. Here, we bridge this gap, by presenting a characterization of the set $\Theta_n$ of the PLMs of UBTs obtained by strengthening Buneman’s results on the tree-realization problem. We extend our study to $Conv(\Theta_n)$, the convex hull of $\Theta_n$ by establishing several polyhedral results, by identifying numerous families of valid inequalities for $Conv(\Theta_n)$, and by determining so a general framework for optimizing over $\Theta_n$. We then shift the focus on the Balanced Minimum Evolution Problem (BMEP), a NP-hard nonlinear optimization problem over $\Theta_n$ that has been much studied in the literature on molecular phylogenetics. Leveraging our characterization and working in an extended space, we present the most compact valid integer linear programming formulation for the BMEP known so far. We show how to refine this formulation by removing redundant constraints as well as how to strengthen it by lifting the valid inequalities for $Conv(\Theta_n)$ discussed before. We also develop novel primal heuristics for the problem as well as separation oracles for some families of combinatorial inequalities describing facets of $Conv(\Theta_n)$. This exercise provides a branch-and-cut algorithm for the BMEP that significantly outperforms the current state-of-the-art. The results presented here provide a new perspective to optimizing over $\Theta_n$ and provide new insights on the combinatorics of the BMEP that may inspire future and more effective exact solution algorithms.