# MurTree: Optimal Classification Trees via Dynamic Programming and Search

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2020.

## Built on by (most cited first, 30 of 63)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2405.14956/) (2024)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)
- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- [MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees](https://mlsanity.com/paper/2309.15312/) (2023)
- [Rule Generation for Classification: Scalability, Interpretability, and Fairness](https://mlsanity.com/paper/2104.10751/) (2021)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [DeepSaDe: Learning Neural Networks that Guarantee Domain Constraint Satisfaction](https://mlsanity.com/paper/2303.01141/) (2023)
- [Leveraging Predictive Equivalence in Decision Trees](https://mlsanity.com/paper/2506.14143/) (2025)
- [SaDe: Learning Models that Provably Satisfy Domain Constraints](https://mlsanity.com/paper/2112.00552/) (2021)
- [On Computing Optimal Tree Ensembles](https://mlsanity.com/paper/2306.04423/) (2023)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [A Generic Complete Anytime Beam Search for Optimal Decision Tree](https://mlsanity.com/paper/2508.06064/) (2025)
- [A Mathematical Programming Approach to Optimal Classification Forests](https://mlsanity.com/paper/2211.10502/) (2022)
- [ODTlearn: A Package for Learning Optimal Decision Trees for Prediction and Prescription](https://mlsanity.com/paper/2307.15691/) (2023)
- [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [Anytime Optimal Decision Tree Learning with Continuous Features](https://mlsanity.com/paper/2601.14765/) (2026)
- [A Nested Genetic Algorithm for Explaining Classification Data Sets with Decision Rules](https://mlsanity.com/paper/2209.07575/) (2022)
- [Fast Optimization of Weighted Sparse Decision Trees for use in Optimal Treatment Regimes and Optimal Policy Design](https://mlsanity.com/paper/2210.06825/) (2022)
- [In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search](https://mlsanity.com/paper/2409.03260/) (2024)
- [DynFrs: An Efficient Framework for Machine Unlearning in Random Forest](https://mlsanity.com/paper/2410.01588/) (2024)

## Abstract (arXiv)

Decision tree learning is a widely used approach in machine learning, favoured in applications that require concise and interpretable models. Heuristic methods are traditionally used to quickly produce models with reasonably high accuracy. A commonly criticised point, however, is that the resulting trees may not necessarily be the best representation of the data in terms of accuracy and size. In recent years, this motivated the development of optimal classification tree algorithms that globally optimise the decision tree in contrast to heuristic methods that perform a sequence of locally optimal decisions. We follow this line of work and provide a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our algorithm supports constraints on the depth of the tree and number of nodes. The success of our approach is attributed to a series of specialised techniques that exploit properties unique to classification trees. Whereas algorithms for optimal classification trees have traditionally been plagued by high runtimes and limited scalability, we show in a detailed experimental study that our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances, providing several orders of magnitude improvements and notably contributing towards the practical realisation of optimal decision trees.