Porcentagens de particionamento do relax and fix e nova proposta de PLI para o problema da filogenia viva com politomia

Abstract

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. The objective of this work is to test the implementation of relax and fix with two matheuristics: sequential (stores the variables in the parts of the partition set in the sequence of the ordered set of the variables themselves), and random (stores the variables randomly in the parts of the partition set) with three different percentages (3%, 5%, and 10%) for the size of the parts of the partition set. The optimization libraries SCIP and Cplex were used to execute the problem, and the matheuristics were incorporated into a branch-and-bound algorithm. The results obtained with the proposed matheuristics did not achieve good bounded values. The higher the percentage, the fewer instances had solutions found, with the sequential matheuristic with 3% in the part size finding a solution in 5 instances. A new integer linear programming model for the living phylogeny problem was also proposed; however, the model was not implemented.