Print Email Facebook Twitter Optimal decision tree using dynamic programming Title Optimal decision tree using dynamic programming: for the algorithm selection problem Author Zeng, Henwei (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor van der Linden, J.G.M. (mentor) Demirović, E. (mentor) Oliehoek, F.A. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science and Engineering Project CSE3000 Research Project Date 2023-02-03 Abstract Several algorithms can often be used to solve a complex problem, such as the SAT problem or the graph coloring problem. Those algorithms differ in terms of speed based on the size or other features of the problem. Some algorithms perform much faster on a small size while others perform noticeably better on a larger instance. The optimization problem in this case is to select the best-performing algorithm based on the problem features, resulting in a much faster overall runtime. This is defined as the algorithm selection problem. Many different approaches have been used to solve this problem, such as constructing optimal decision trees. However, there is little published data on using optimal decision trees for algorithm selection and one study reveals a problem in finding a feasible solution on a large number of problem instances. We provide new insights into solving algorithm selection using a dynamic programming approach. The motivation to use this novel approach is that recent studies suggest it has lower scalability issues compared to the traditional optimal decision tree algorithms, due to several efficient techniques such as caching and frequency counting method. The investigation has shown that compared to the integer programming method, the dynamic programming approach is significantly faster and is able to solve large problem instances. Subject Algorithm SelectionOptimal Decision TreeDynamic Programming To reference this document use: http://resolver.tudelft.nl/uuid:21c2df62-18f3-416d-8b06-8d81211c255f Part of collection Student theses Document type bachelor thesis Rights © 2023 Henwei Zeng Files PDF Research_project_Final_Paper.pdf 451.69 KB Close viewer /islandora/object/uuid:21c2df62-18f3-416d-8b06-8d81211c255f/datastream/OBJ/view