Optimizing over path-length matrices of unrooted binary trees

• 成果类型: Article; Early Access
• 署名作者: Catanzaro, Daniele; Pesenti, Raffaele; Sapucaia, Allan; Wolsey, Laurence
• 署名单位: Universite Catholique Louvain; Universita Ca Foscari Venezia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02226-z
• 发表日期: 2025
• 关键词: minimum evolution problem; inference; algorithm; geometry; facets; MODEL

摘要

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 >= 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 Theta(n) 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 NP-hard nonlinear optimization problem over Theta n 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.