On the balanced minimum evolution polytope

Catanzaro, Daniele;Pesenti, Raffaele;Wolsey, Laurence
(2020) Discrete Optimization — Vol. 36, p. 100570 (2020)

Files

Rep3096.pdf
  • Open Access
  • Adobe PDF
  • 3.06 MB
Download

Details

Authors
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 poytope, 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Catanzaro, D., Pesenti, R., & Wolsey, L. (2020). On the balanced minimum evolution polytope. Discrete Optimization, 36, 100570. https://doi.org/10.1016/j.disopt.2020.100570 (Original work published 2020)