Optimal decision trees for the Algorithm Selection Problem
A dynamic programming approach
G. Segalini (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Emir Demirović – Mentor (TU Delft - Algorithmics)
Jacobus G.M. van der Linden – Mentor (TU Delft - Algorithmics)
Burcu Kulahcioglu Kulahcioglu Ozkan – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem.
Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no guarantees of optimality, or not interpretable models that could be used to gain insights into the nature of the problem.
In this work we propose a dynamic programming method to build Optimal Decision Trees to solve the Algorithm Selection Problem, giving us an interpretable model that is globally optimal over the training dataset. We also show that this method is orders of magnitude faster in training trees that are identical to the current state-of-the-art and propose possible improvements for future work.