Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach
This work addresses the problem of building interpretable and efficient classification trees for machine learning practitioners, offering an incremental improvement with practical scalability enhancements.
The paper tackles the challenge of globally optimizing decision trees for interpretable machine learning by proposing a mixed-integer programming framework that handles nonlinear metrics like the F1-score to address class imbalance, achieving strong predictive performance and reduced solution times on 50 benchmark datasets.
Global optimization of decision trees is a long-standing challenge in combinatorial optimization, yet such models play an important role in interpretable machine learning. Although the problem has been investigated for several decades, only recent advances in discrete optimization have enabled practical algorithms for solving optimal classification tree problems on real-world datasets. Mixed-integer programming (MIP) offers a high degree of modeling flexibility, and we therefore propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics, such as the F1-score, that explicitly addresses class imbalance. To improve scalability, we develop problem-specific acceleration techniques, including a tailored branch-and-cut algorithm, an instance-reduction scheme, and warm-start strategies. We evaluate the proposed approach on 50 benchmark datasets. The computational results show that the framework can efficiently optimize nonlinear metrics while achieving strong predictive performance and reduced solution times compared with existing methods.