Defesa de doutorado de Matheus Guedes, dia 13/12/19 as 09 horas, sala de seminários do DECOM

Defesa de doutorado de Matheus Guedes, dia 13/12/19 as 09 horas, sala de seminários do DECOM

Título: Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches
Resumo: Even though it is well known that for most relevant computational problems different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this thesis, we propose Integer Programming based approaches to build decision trees for the Algorithm Selection Problem. These techniques the automation of three crucial decisions: (i) discerning the most important problem features to determine problem classes; (ii) grouping the problems into classes and (iii) select the best algorithm configuration for each class. We tested our approach from several perspectives: (i) univariate approach, where for each branch node, only one cutoff point of a feature is chosen; (ii) Multivariate approach, where for each branch node, weights for multiple features are used (oblique decision trees). In addition, considering the current scenario where the number of cores per machine has increased considerably, we also propose a new approach based on recommendation of concurrent algorithms. Thus, for each leaf node, we tested the recommendation of 1, 2 and 3 algorithm configurations. To evaluate this new approach, extensive computational experiments were executed using two bases: the first base considers the linear programming algorithms implemented in the COIN-OR Branch & Cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. The second base were obtained from the Aslib library and considers the Constraint Satisfaction Problem (CSP). The results exceeded our expectations. Considering the first base, while
selecting the single best solver across all instances decreased the total running time by 2%, our approach decreased the total running time by 68% (univariate approach) and by 85% (multivariate approach using three algorithms configuration per leaf node) on average across 10-fold cross validation experiments. These results indicate that our method generalizes quite well and does not overfit.

Banca: Prof. Dr. Christian Clemens Blum; Prof. Dr. Luiz Henrique de Campos Merschmann; Prof. Dr. Rodrigo Cesar Pedrosa Silva; Prof. Dr. Túlio Ângelo Machado Toffolo e Prof. Dr. Haroldo Gambini.