TY - JOUR
T1 - On the Balanced Minimum Evolution polytope
AU - Catanzaro, Daniele
AU - Pesenti, Raffaele
AU - Wolsey, Laurence
PY - 2020/5/1
Y1 - 2020/5/1
N2 - 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.
AB - 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.
KW - Balanced Minimum Evolution
KW - Polyhedral combinatorics
KW - Facet-defining inequalities
KW - Manifold of unrooted binary trees
KW - Kraft’s equality
KW - Enumeration of trees
U2 - 10.1016/j.disopt.2020.100570
DO - 10.1016/j.disopt.2020.100570
M3 - Article
SN - 1572-5286
VL - 36
JO - Discrete Optimization
JF - Discrete Optimization
M1 - 100570
ER -