# Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound

arXiv: https://arxiv.org/abs/2501.07903 · HTML: https://mlsanity.com/paper/2501.07903/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2025.

## Built on by (most cited first, 6 of 6)

- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- [Optimal hypersurface decision trees](https://mlsanity.com/paper/2509.12057/) (2025)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)
- [Adaptive Multi-Branching for Shallow Decision Tree Induction](https://mlsanity.com/paper/2608.29262/) (2026)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)
- [An Exact Junction-Tree Extended Formulation for Optimal Classification Trees](https://mlsanity.com/paper/2609.24741/) (2026)

## Abstract (arXiv)

Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.