Decision trees for the algorithm selection problem : integer programming based approaches.

Abstract

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.