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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${\varTheta _n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Θ</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal{N}\mathcal{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">N</mi> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation>-hard nonlinear optimization problem over <InlineEquation ID="IEq4"> <EquationSource Format="TEX">${\varTheta _n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Θ</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> 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.

Optimizing over path-length matrices of unrooted binary trees

期刊论文
发表日期：

2025年4月25日

查看全文

Daniele Catanzaro,
Raffaele Pesenti,
Allan Sapucaia,
Laurence Wolsey

摘要

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\ge 3$ $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 ${\varTheta _n}$ $Θ_{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 $\mathcal{N}\mathcal{P}$ $N P$ -hard nonlinear optimization problem over ${\varTheta _n}$ $Θ_{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.