{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T22:44:20Z","timestamp":1773528260257,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1007\/s10107-025-02226-z","type":"journal-article","created":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T05:37:58Z","timestamp":1745559478000},"page":"453-505","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimizing over path-length matrices of unrooted binary trees"],"prefix":"10.1007","volume":"215","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9427-1562","authenticated-orcid":false,"given":"Daniele","family":"Catanzaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raffaele","family":"Pesenti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Sapucaia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurence","family":"Wolsey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"2226_CR1","volume-title":"The Traveling Salesman Problem: A Compuational Study","author":"DL Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: A Compuational Study. Princeton University Press, NJ (2006)"},{"key":"2226_CR2","doi-asserted-by":"publisher","first-page":"1845","DOI":"10.1016\/j.cor.2011.02.020","volume":"38","author":"R Aringhieri","year":"2011","unstructured":"Aringhieri, R., Catanzaro, D., Di Summa, M.: Optimal solutions for the balanced minimum evolution problem. Comput. Oper. Res. 38, 1845\u20131854 (2011)","journal-title":"Comput. Oper. Res."},{"key":"2226_CR3","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/aama.2001.0759","volume":"27","author":"LJ Billera","year":"2001","unstructured":"Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27, 733\u2013767 (2001)","journal-title":"Adv. Appl. Math."},{"key":"2226_CR4","unstructured":"Boost. Boost C++ libraries 1.82.0 (2023)"},{"key":"2226_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1093\/oxfordjournals.molbev.a026231","volume":"17","author":"WJ Bruno","year":"2000","unstructured":"Bruno, W.J., Socci, M.D., Halpern, A.L.: Weighted neighbor-joining: a likelihood-based approach to distance-based phylogeny reconstruction. Mol. Biol. Evol. 17, 189\u2013197 (2000)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR6","first-page":"387","volume-title":"Archaeological and Historical Science","author":"P Buneman","year":"1971","unstructured":"Buneman, P.: The recovery of trees from measure of dissimilarities. In: Hodson, F.R., Kendall, D.G., Tautu, P. (eds.) Archaeological and Historical Science, pp. 387\u2013395. Edinburgh University Press, Edinburgh (1971)"},{"key":"2226_CR7","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","volume":"17","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A note on the metric properties of trees. J. Comb. Theory 17, 48\u201350 (1974)","journal-title":"J. Comb. Theory"},{"key":"2226_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2007.03.009","volume":"382","author":"S Caminiti","year":"2007","unstructured":"Caminiti, S., Finocchi, I., Petreschi, R.: On coding labeled trees. Theor. Comput. Sci. 382, 97\u2013108 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"2226_CR9","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1002\/net.20280","volume":"53","author":"D Catanzaro","year":"2009","unstructured":"Catanzaro, D.: The minimum evolution problem: overview and classification. Networks 53, 112\u2013125 (2009)","journal-title":"Networks"},{"key":"2226_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-1-4419-6800-5_8","volume-title":"Mathematical Approaches to Polymer Sequence Analysis and Related Problems","author":"D Catanzaro","year":"2011","unstructured":"Catanzaro, D.: Estimating Phylogenies From Molecular Data. In: Bruni, R. (ed.) Mathematical Approaches to Polymer Sequence Analysis and Related Problems, pp. 149\u2013176. Springer, NY (2011)"},{"key":"2226_CR11","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.ejor.2015.02.019","volume":"244","author":"D Catanzaro","year":"2015","unstructured":"Catanzaro, D., Aringhieri, R., di Summa, M., Pesenti, R.: A branch-price-and-cut algorithm for the minimum evolution problem. Eur. J. Oper. Res. 244, 753\u2013765 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"2226_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2021.08.004","volume":"300","author":"D Catanzaro","year":"2022","unstructured":"Catanzaro, D., Frohn, M., Gascuel, O., Pesenti, R.: A tutorial on the balanced minimum evolution problem. Eur. J. Oper. Res. 300, 1\u201319 (2022)","journal-title":"Eur. J. Oper. Res."},{"key":"2226_CR13","doi-asserted-by":"crossref","unstructured":"Catanzaro, D., Frohn, M., Gascuel, O., Pesenti, R.: A massively parallel branch- &-bound algorithm for the balanced minimum evolution problem. Comput. Oper. Res. (2023, to appear)","DOI":"10.1016\/j.cor.2023.106308"},{"key":"2226_CR14","first-page":"145","volume":"2","author":"D Catanzaro","year":"2006","unstructured":"Catanzaro, D., Gatto, L., Milinkovitch, M.: Assessing the applicability of the GTR nucleotide substitution model through simulations. Evol. Bioinform. 2, 145\u2013155 (2006)","journal-title":"Evol. Bioinform."},{"key":"2226_CR15","doi-asserted-by":"publisher","first-page":"1789","DOI":"10.1016\/j.dam.2013.03.012","volume":"161","author":"D Catanzaro","year":"2013","unstructured":"Catanzaro, D., Labb\u00e9, M., Pesenti, R.: The balanced minimum evolution problem under uncertain data. Discrete Appl. Math. 161, 1789\u20131804 (2013)","journal-title":"Discrete Appl. Math."},{"key":"2226_CR16","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1287\/ijoc.1110.0455","volume":"24","author":"D Catanzaro","year":"2012","unstructured":"Catanzaro, D., Labb\u00e9, M., Pesenti, R., Salazar-Gonz\u00e1les, J.J.: The balanced minimum evolution problem. Inform. J. Comput. 24, 276\u2013294 (2012)","journal-title":"Inform. J. Comput."},{"key":"2226_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.cor.2019.05.001","volume":"109","author":"D Catanzaro","year":"2019","unstructured":"Catanzaro, D., Pesenti, R.: Enumerating vertices of the balanced minimum evolution polytope. Comput. Oper. Res. 109, 209\u2013217 (2019)","journal-title":"Comput. Oper. Res."},{"key":"2226_CR18","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1093\/bioinformatics\/btk001","volume":"22","author":"D Catanzaro","year":"2006","unstructured":"Catanzaro, D., Pesenti, R., Milinkovitch, M.: A non-linear optimization procedure to estimate distances and instantaneous substitution rate matrices under the GTR model. Bioinformatics 22, 708\u2013715 (2006)","journal-title":"Bioinformatics"},{"key":"2226_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2020.100570","volume":"36","author":"D Catanzaro","year":"2020","unstructured":"Catanzaro, D., Pesenti, R., Wolsey, L.A.: On the balanced minimum evolution polytope. Discrete Optim. 36, 1\u201333 (2020)","journal-title":"Discrete Optim."},{"key":"2226_CR20","doi-asserted-by":"publisher","first-page":"1202","DOI":"10.1007\/s11538-010-9556-x","volume":"73","author":"MA Cueto","year":"2011","unstructured":"Cueto, M.A., Matsen, F.A.: Polyhedral geometry of phylogenetic rogue taxa. Bull. Math. Biol. 73, 1202\u20131226 (2011)","journal-title":"Bull. Math. Biol."},{"key":"2226_CR21","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1093\/molbev\/msh049","volume":"21","author":"R Desper","year":"2004","unstructured":"Desper, R., Gascuel, O.: Theoretical foundations of the balanced minimum evolution method of phylogenetic inference and its relationship to the weighted least-squares tree fitting. Mol. Biol. Evol. 21, 587\u2013598 (2004)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-3-1","volume":"3","author":"K Eickmeyer","year":"2008","unstructured":"Eickmeyer, K., Huggins, P., Pachter, L., Yoshida, R.: On the optimality of the neighbor-joining algorithm. Algor. Mol. Biol. 3, 1\u201311 (2008)","journal-title":"Algor. Mol. Biol."},{"key":"2226_CR23","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Sunderland, MA (2004)"},{"key":"2226_CR24","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.orl.2011.10.003","volume":"40","author":"S Fiorini","year":"2012","unstructured":"Fiorini, S., Joret, G.: Approximating the balanced minimum evolution problem. Oper. Res. Lett. 40, 31\u201335 (2012)","journal-title":"Oper. Res. Lett."},{"key":"2226_CR25","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s00285-015-0957-1","volume":"73","author":"S Forcey","year":"2015","unstructured":"Forcey, S., Keefe, L., Sands, W.: Facets of the balanced minimal evolution polytope. J. Math. Biol. 73, 447\u2013468 (2015)","journal-title":"J. Math. Biol."},{"key":"2226_CR26","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1007\/s11538-017-0264-7","volume":"79","author":"S Forcey","year":"2017","unstructured":"Forcey, S., Keefe, L., Sands, W.: Split-facets for balanced minimal evolution polytopes and the permutoassociahedron. Bull. Math. Biol. (in press) 79, 975\u2013994 (2017)","journal-title":"Bull. Math. Biol. (in press)"},{"key":"2226_CR27","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.ejor.2016.06.014","volume":"256","author":"B Fortz","year":"2017","unstructured":"Fortz, B., Oliveira, O., Requejo, C.: Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem. Eur. J. Oper. Res. 256, 242\u2013251 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"2226_CR28","doi-asserted-by":"publisher","first-page":"2321","DOI":"10.1007\/s11590-020-01677-x","volume":"15","author":"M Frohn","year":"2021","unstructured":"Frohn, M.: On the approximability of the fixed-tree balanced minimum evolution problem. Optim. Lett. 15, 2321\u20132329 (2021)","journal-title":"Optim. Lett."},{"key":"2226_CR29","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1093\/oxfordjournals.molbev.a025808","volume":"14","author":"O Gascuel","year":"1997","unstructured":"Gascuel, O.: BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data. Mol. Biol. Evol. 14, 685\u2013695 (1997)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR30","doi-asserted-by":"crossref","unstructured":"Gascuel, O.: Concerning the NJ algorithm and its unweighted version, UNJ, in Mathematical Hierarchies and Biology. In: Mirkin, B.,\u00a0McMorris, F.,\u00a0Roberts, F., Rzhetsky, A. (eds.) American Mathematical Society, Providence, RI, pp.\u00a0149\u2013170 (1997)","DOI":"10.1090\/dimacs\/037\/09"},{"key":"2226_CR31","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198566106.001.0001","volume-title":"Mathematics of Evolution and Phylogeny","author":"O Gascuel","year":"2005","unstructured":"Gascuel, O.: Mathematics of Evolution and Phylogeny. Oxford University Press, New York, NY (2005)"},{"key":"2226_CR32","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1093\/molbev\/msl072","volume":"23","author":"O Gascuel","year":"2006","unstructured":"Gascuel, O., Steel, M.A.: Neighbor-joining revealed. Mol. Biol. Evol. 23, 1997\u20132000 (2006)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR33","unstructured":"Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2023)"},{"key":"2226_CR34","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1090\/qam\/184873","volume":"22","author":"SL Hakimi","year":"1964","unstructured":"Hakimi, S.L., Yau, S.S.: Distance matrix of a graph and its realizability. Q. Appl. Math. 22, 305\u2013317 (1964)","journal-title":"Q. Appl. Math."},{"key":"2226_CR35","doi-asserted-by":"publisher","first-page":"2627","DOI":"10.1007\/s11538-011-9640-x","volume":"73","author":"DC Haws","year":"2011","unstructured":"Haws, D.C., Hodge, T.L., Yoshida, R.: Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope. Bull. Math. Biol. 73, 2627\u20132648 (2011)","journal-title":"Bull. Math. Biol."},{"key":"2226_CR36","doi-asserted-by":"crossref","unstructured":"Hendy, M.D., Penny, D.: Branch and bound algorithms to determine minimal evolutionary trees. Math. Biosci. (1982)","DOI":"10.1016\/0025-5564(82)90027-X"},{"key":"2226_CR37","first-page":"119","volume":"85","author":"MM Kapranov","year":"1993","unstructured":"Kapranov, M.M.: The permutoassociahedron. Mac Lane\u2019s coherence theorem and asymptotic zones for the KZ equation, Journal of Pure and Applied Algebra 85, 119\u2013142 (1993)","journal-title":"Mac Lane\u2019s coherence theorem and asymptotic zones for the KZ equation, Journal of Pure and Applied Algebra"},{"key":"2226_CR38","unstructured":"Kraft, L.G.: A device for quantizing, grouping, and coding amplitude modulated pulses. Master\u2019s thesis, Electrical Engineering Department, Massachussetts Institute of Technology (1949)"},{"key":"2226_CR39","doi-asserted-by":"publisher","first-page":"2798","DOI":"10.1093\/molbev\/msv150","volume":"32","author":"V Lefort","year":"2015","unstructured":"Lefort, V., Desper, R., Gascuel, O.: FastME 2.0: A comprehensive, accurate, and fast distance-based phylogeny inference program. Mol. Biol. Evol. 32, 2798\u20132800 (2015)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR40","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1109\/TIT.1956.1056818","volume":"2","author":"B McMillan","year":"1956","unstructured":"McMillan, B.: Two inequalities implied by unique decipherability. IEEE Trans. Inf. Theory 2, 115\u2013116 (1956)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2226_CR41","volume-title":"Probabilistic Machine Learning","author":"KP Murphy","year":"2022","unstructured":"Murphy, K.P.: Probabilistic Machine Learning. The MIT Press, London (2022)"},{"key":"2226_CR42","volume-title":"Molecular Evolution: A Phylogenetic Approach","author":"RDM Page","year":"1998","unstructured":"Page, R.D.M., Holmes, E.C.: Molecular Evolution: A Phylogenetic Approach. Blackwell Science, Oxford (1998)"},{"key":"2226_CR43","unstructured":"Pardi, F.: Algorithms on Phylogenetic Trees, PhD thesis, University of Cambridge, UK, (2009)"},{"key":"2226_CR44","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/qam\/414405","volume":"30","author":"AN Patrinos","year":"1972","unstructured":"Patrinos, A.N., Hakimi, S.L.: The distance matrix of a graph and its tree realization. Q. Appl. Math. 30, 255\u2013269 (1972)","journal-title":"Q. Appl. Math."},{"key":"2226_CR45","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s002390010065","volume":"51","author":"Y Pauplin","year":"2000","unstructured":"Pauplin, Y.: Direct calculation of a tree length using a distance matrix. J. Mol. Evol. 51, 41\u201347 (2000)","journal-title":"J. Mol. Evol."},{"key":"2226_CR46","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0021-9800(69)80092-X","volume":"6","author":"JMSS Pereira","year":"1969","unstructured":"Pereira, J.M.S.S.: A note on the tree realizability of a distance matrix. J. Comb. Theory 6, 303\u2013310 (1969)","journal-title":"J. Comb. Theory"},{"key":"2226_CR47","first-page":"364","volume":"41","author":"V Reiner","year":"1994","unstructured":"Reiner, V., Ziegler, G.M.: Coxeter-associahedra, Zuse Institute Berlin (ZIB), Berlin, Takustrasse 7, 14195. Germany 41, 364\u2013393 (1994)","journal-title":"Germany"},{"key":"2226_CR48","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4, 406\u2013425 (1987)","journal-title":"Mol. Biol. Evol."},{"key":"2226_CR49","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.A.: Phylogenetics. Oxford University Press, New York, NY (2003)"},{"key":"2226_CR50","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1016\/S0196-8858(03)00098-8","volume":"32","author":"C Semple","year":"2004","unstructured":"Semple, C., Steel, M.A.: Cyclic permutations and evolutionary trees. Adv. Appl. Math. 32, 669\u2013680 (2004)","journal-title":"Adv. Appl. Math."},{"key":"2226_CR51","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974485","volume-title":"Phylogeny: Discrete and Random Processes in Evolution","author":"M Steel","year":"2016","unstructured":"Steel, M.: Phylogeny: Discrete and Random Processes in Evolution. Society for Industrial and Applied Mathematics, Philadelphia, PA (2016)"},{"key":"2226_CR52","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0022-5193(77)90351-4","volume":"64","author":"MS Waterman","year":"1977","unstructured":"Waterman, M.S., Smith, T.F., Singh, M., Beyer, W.A.: Additive evolutionary trees. J. Theor. Biol. 64, 199\u2013213 (1977)","journal-title":"J. Theor. Biol."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02226-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02226-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02226-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T14:02:07Z","timestamp":1768053727000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02226-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,25]]},"references-count":52,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["2226"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02226-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,25]]},"assertion":[{"value":"23 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This manuscript fully complies with the Ethical Standards of Mathematical Programming. The authors declare no Conflict of interest\/Conflict of interest of any sort and fully adhere to the authorship principles and practices. All the authors equally concurred to develop the theoretical and methodological study as well as to writing the article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with the ethical standard of the journal"}}]}}