Matheurísticas para o Problema da Filogenia Viva com Politomia

Abstract

A phylogenetic tree shows the evolutionary relationship between living beings or objects, such as documents shared online. A living phylogenetic tree with polytomy is a tree in which its internal nodes can include living objects and an internal node can generate two or more descendants. Trees can be obtained through a distance matrix. The objective of this work is to find an algorithm, using integer linear programming and matheuristics, that given a distance matrix, constructs a living phylogenetic tree with polytomy in which the distance between objects in the tree is as close as possible to the distance between them in the matrix. To solve the problem, matheuristics based on the relax-and-fix method were proposed and implemented, using the SCIP and Cplex optimization libraries, and incorporated as heuristics in a branch-and-bound algorithm. Three criteria were proposed for partitioning variables: sequential (stores the variables in the parts of the partition set in sequence from the ordered set of the variables themselves), random (stores the variables randomly in the parts of the partition set), and PAI (stores the variables related to the edges that arrive at the vertices first, one part of the partition set for each vertex), which prioritizes the variables related to the edges that arrive at a vertex. The results obtained with the proposed matheuristics did not achieve good bound values and did not find viable solutions in instances with more than 10 objects. However, the tests performed show that the sequential matheuristic provides the best bounds when compared to the others.