Optimal decision trees for the Algorithm Selection Problem

Optimal decision trees for the Algorithm Selection Problem: A dynamic programming approach

Segalini, Giulio (TU Delft Electrical Engineering, Mathematics and Computer Science)

Demirović, E. (mentor)
van der Linden, J.G.M. (mentor)
Kulahcioglu Ozkan, Burcu (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-06-22

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.

Algorithms
Decision Trees
Algorithm Selection
Dynamic Programming
Optimal Decision Tree

http://resolver.tudelft.nl/uuid:315aebf3-5c90-47a7-a3ee-7bde2bab6e9c

Student theses

bachelor thesis

© 2023 Giulio Segalini