A Decomposable Branch-and-Price Formulation for Optimal Classification Trees by Elif Rana Yöner
Thesis Advisor: Assoc. Prof. Özlem Karsu
Co-Advisor: Asst. Prof. Taghi Khaniyev
Date: July 23 Tuesday 2024
Time: 15:00
Place: EA-202 (and Zoom)
This is an online seminar. To obtain event details please send a message to department
Abstract:
Construction of Optimal Classification Trees (OCTs) using mixed-integer programs, is a promising approach as it returns a tree with minimum classification error. Yet solving integer programs to optimality is known to be computationally costly, especially as the size of the instance and the depth of the tree grows, calling for efficient solution methods. Our research presents an approach to solving these programs to optimality using a novel Branch-and-Price algorithm. We model the classification tree using a “pattern-based” formulation, deciding which feature each leaf must be split upon at each level’s decision node. Our results show promising results, illustrating the power of decomposition in the domain of binary OCTs.