# Optimal Generalized Decision Trees via Integer Programming

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2016.

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

- [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Fair Decision Rules for Binary Classification](https://mlsanity.com/paper/2107.01325/) (2021)
- [Predicting Barge Presence and Quantity on Inland Waterways using Vessel Tracking Data: A Machine Learning Approach](https://mlsanity.com/paper/2501.00615/) (2024)
- [Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules](https://mlsanity.com/paper/2503.01455/) (2025)
- [Dive into Decision Trees and Forests: A Theoretical Demonstration](https://mlsanity.com/paper/2101.08656/) (2021)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)

## Abstract (arXiv)

Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mixed integer programming formulation to construct optimal decision trees of a prespecified size. We take the special structure of categorical features into account and allow combinatorial decisions (based on subsets of values of features) at each node. Our approach can also handle numerical features via thresholding. We show that very good accuracy can be achieved with small trees using moderately-sized training sets. The optimization problems we solve are tractable with modern solvers.