# Mixed integer linear optimization formulations for learning optimal binary classification trees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 102 references that are in the map.
- First posted on arXiv 10 Jun 2022.

## Builds on (most cited first, 24 of 24)

- [Stable Architectures for Deep Neural Networks](https://mlsanity.com/paper/1705.03341/) (2017)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Deep Neural Decision Trees](https://mlsanity.com/paper/1806.06988/) (2018)
- [FAHT: An Adaptive Fairness-aware Decision Tree Classifier](https://mlsanity.com/paper/1907.07237/) (2019)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [How fair can we go in machine learning? Assessing the boundaries of fairness in decision trees](https://mlsanity.com/paper/2006.12399/) (2020)
- [Neural Decision Trees](https://mlsanity.com/paper/1702.07360/) (2017)
- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Graph and graphon neural network stability](https://mlsanity.com/paper/2010.12529/) (2020)
- [Oblique Decision Trees from Derivatives of ReLU Networks](https://mlsanity.com/paper/1909.13488/) (2019)
- [HHCART: An Oblique Decision Tree](https://mlsanity.com/paper/1504.03415/) (2015)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Fair Tree Classifier using Strong Demographic Parity](https://mlsanity.com/paper/2110.09295/) (2021)
- [Identifying Properties of Real-World Optimisation Problems through a Questionnaire](https://mlsanity.com/paper/2011.05547/) (2020)
- [Automatic detection of abnormal EEG signals using wavelet feature extraction and gradient boosting decision tree](https://mlsanity.com/paper/2012.10034/) (2020)
- [A geometric way to build strong mixed-integer programming formulations](https://mlsanity.com/paper/1811.10409/) (2018)
- [Conflict-Driven Heuristics for Mixed Integer Programming](https://mlsanity.com/paper/1902.02615/) (2019)

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

- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees](https://mlsanity.com/paper/2408.01297/) (2024)
- [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)

Decision trees are powerful tools for classification and regression that attract many researchers working in the burgeoning area of machine learning. One advantage of decision trees over other methods is their interpretability, which is often preferred over other higher accuracy methods that are relatively uninterpretable. A binary classification tree has two types of vertices: (i) branching vertices which have exactly two children and where datapoints are assessed on a set of discrete features; and (ii) leaf vertices at which datapoints are given a discrete prediction. An optimal binary classification tree can be obtained by solving a biobjective optimization problem that seeks to (i) maximize the number of correctly classified datapoints and (ii) minimize the number of branching vertices. In this paper, we propose four mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees: two flow-based formulations and two-cut based formulations. We provide theoretical comparisons between our proposed formulations and the strongest flow-based MILO formulation of Aghaei et al. (2021). We conduct experiments on 13 publicly available datasets to show the models' ability to scale and the strength of a biobjective approach using Pareto frontiers. Our code and data are available on GitHub.