Decision trees for the algorithm selection problem : integer programming based approaches.
Nenhuma Miniatura disponível
Data
2019
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
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 allow 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 different perspectives: (i) univariate approach, where for each branch
node, only one cutoff point of a feature is chosen and (ii) multivariate approach, where
for each branch node, weights for multiple features are used (oblique decision trees).
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. To evaluate our approaches, extensive computational experiments were executed using a dataset that considers the linear programming algorithms implemented in
the COIN-OR Branch & Cut solver across a comprehensive set of instances, including
all MIPLIB benchmark instances. We also conducted experiments with the scenarios/-
datasets of the Open Algorithm Selection Challenge (OASC) held in 2017. Considering
the first dataset and a 10-fold cross validation experiment, while selecting the single
best solver across all instances decreased the total running time by 2%, our univariate
approach decreased the total running time by 68% and using the multivariate approach,
the total running time is decreased by 72%. An even greater performance gain can be
obtained using concurrent algorithms, something not yet explored in the literature. For
our experiments, using three algorithm configurations per leaf node, the total running
time is decreased by 85%. These results indicate that our method generalizes quite well
and does not overfit. Considering the results obtained using the scenarios of the OASC,
the experimental results showed that our decision trees can produce better results than
less interpretable models, such as random forest, which has been extensively used for
algorithm recommendation.
Descrição
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Palavras-chave
Algoritmos de computador, Mineração de dados - computação, Programação inteira
Citação
VILAS BOAS, Matheus Guedes. Decision trees for the algorithm selection problem:
integer programming based approaches. 2019. 70 f. Tese (Doutorado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2019.