On the Balanced Minimum Evolution polytope

Daniele Catanzaro, Raffaele Pesenti, Laurence Wolsey

Research output: Contribution to journalArticlepeer-review

Abstract

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the characterization of a number of facets of its convex hull (also referred to as the BMEP polytope) as well as the discovery of connections between this polytope and the permutoassociahedron. In this article, we extend these studies, by presenting new results concerning some fundamental characteristics of the BMEP polytope, new facet-defining inequalities in the case of six or more taxa, a number of valid inequalities, and a polynomial time oracle to recognize its vertices. Our aim is to broaden understanding of the polyhedral combinatorics of the BMEP with a view to developing new and more effective exact solution algorithms.
Original languageEnglish
Article number100570
JournalDiscrete Optimization
Volume36
DOIs
Publication statusPublished - 1 May 2020

Keywords

  • Balanced Minimum Evolution
  • Polyhedral combinatorics
  • Facet-defining inequalities
  • Manifold of unrooted binary trees
  • Kraft’s equality
  • Enumeration of trees

Cite this