Optimal decision trees for the Algorithm Selection Problem

A dynamic programming approach

Bachelor thesis (2023)

Authors

G. Segalini Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (supervisor 1)
J.G.M. van der Linden Algorithmics - EEMCS (supervisor 1)
Burcu Kulahcioglu Ozkan Software Engineering - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Giulio Segalini
Optimal Decision Tree Algorithm Selection Dynamic Programming Algorithms Decision Trees
More Info
expand_more

Published Date

22-06-2023

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.