Master of Science, University of Akron, 2017, Applied Mathematics

Combinatorial methods have proved to be useful in generating relaxations of polytopes in various areas of mathematical programming. In this work, we propose a discrete-integer linear programming model for a recent version of the Phylogeny Estimation Problem (PEP), known as the Balanced Minimal Evolution Method (BME). We begin by examining an object known as the Balanced Minimal Evolution Polytope and several classes of geometric constraints that result in its relaxation. We use this information to develop the linear program and propose two Branch and Bound algorithms to solve the model. The second algorithm takes advantage of a heuristic known as a large neighborhood search. We provide experimental results for both algorithms, using perfect and noisy data, as well as suggestions for further improvement.

Committee: Stefan Forcey Dr. (Advisor); Malena Espanol Dr. (Committee Member); Patrick Wilber Dr. (Committee Member) Subjects: Applied Mathematics; Biology