# Learning Optimal Classification Trees: Strong Max-Flow Formulations

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

## Key facts

- Cited by 11 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 21 Feb 2020.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Optimal Decision Diagrams for Classification](https://mlsanity.com/paper/2205.14500/) (2022)
- [Constrained Prescriptive Trees via Column Generation](https://mlsanity.com/paper/2207.10163/) (2022)
- [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023)
- [Improving Stability in Decision Tree Models](https://mlsanity.com/paper/2305.17299/) (2023)
- [Rolling Lookahead Learning for Optimal Classification Trees](https://mlsanity.com/paper/2304.10830/) (2023)
- [Experiments with Optimal Model Trees](https://mlsanity.com/paper/2503.12902/) (2025)
- [On multivariate randomized classification trees: l0-based sparsity, VC~dimension and decomposition methods](https://mlsanity.com/paper/2112.05239/) (2021)
- [Improving the Validity of Decision Trees as Explanations](https://mlsanity.com/paper/2306.06777/) (2023)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)

## Abstract (arXiv)

We consider the problem of learning optimal binary classification trees. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic approaches and the tremendous improvements in mixed-integer programming (MIP) technology. Yet, existing approaches from the literature do not leverage the power of MIP to its full extent. Indeed, they rely on weak formulations, resulting in slow convergence and large optimality gaps. To fill this gap in the literature, we propose a flow-based MIP formulation for optimal binary classification trees that has a stronger linear programming relaxation. Our formulation presents an attractive decomposable structure. We exploit this structure and max-flow/min-cut duality to derive a Benders' decomposition method, which scales to larger instances. We conduct extensive computational experiments on standard benchmark datasets on which we show that our proposed approaches are 50 times faster than state-of-the art MIP-based techniques and improve out of sample performance up to 13.8%.