On the Balanced Minimum Evolution polytope

Daniele Catanzaro; Raffaele Pesenti; Laurence Wolsey

doi:10.1016/j.disopt.2020.100570

On the Balanced Minimum Evolution polytope

Daniele Catanzaro, Raffaele Pesenti, Laurence Wolsey

Research output: Contribution to journal › Article › peer-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 language	English
Article number	100570
Journal	Discrete Optimization
Volume	36
DOIs	https://doi.org/10.1016/j.disopt.2020.100570
Publication status	Published - 1 May 2020

Keywords

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

Access to Document

10.1016/j.disopt.2020.100570

http://www.sciencedirect.com/science/article/pii/S1572528620300049

Cite this

@article{6f94227b33e0407aafa4d250f459700f,

title = "On the Balanced Minimum Evolution polytope",

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.",

keywords = "Balanced Minimum Evolution, Polyhedral combinatorics, Facet-defining inequalities, Manifold of unrooted binary trees, Kraft{\textquoteright}s equality, Enumeration of trees",

author = "Daniele Catanzaro and Raffaele Pesenti and Laurence Wolsey",

year = "2020",

month = may,

day = "1",

doi = "10.1016/j.disopt.2020.100570",

language = "English",

volume = "36",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

}

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 -