Optimizing over Path-Length Matrices of Unrooted Binary Trees

Daniele Catanzaro (), Raffaele Pesenti (), Allan Sapucaia () and Laurence Wolsey ()
Additional contact information
Daniele Catanzaro: Université catholique de Louvain, LIDAM/CORE, Belgium
Raffaele Pesenti: University Ca’ Foscari
Allan Sapucaia: Université catholique de Louvain, LIDAM/CORE, Belgium
Laurence Wolsey: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2023020, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Combinatorial optimization; integer programming; polyhedral combinatorics; branch-&-cut; path-length matrices; unrooted binary trees; tree realization; Kraft’s equality; Buneman’s four-point condition; balanced minimum evolution (search for similar items in EconPapers)
Pages: 31
Date: 2023-07-21
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2023020

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().