# A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees

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

## Key facts

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

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

- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Differentiable Rule Induction with Learned Relational Features](https://mlsanity.com/paper/2201.06515/) (2022)
- [Constrained Prescriptive Trees via Column Generation](https://mlsanity.com/paper/2207.10163/) (2022)
- [Optimal Survival Trees: A Dynamic Programming Approach](https://mlsanity.com/paper/2401.04489/) (2024)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Flexible Modeling and Multitask Learning using Differentiable Tree Ensembles](https://mlsanity.com/paper/2205.09717/) (2022)
- [bsnsing: A decision tree induction method based on recursive optimal boolean rule composition](https://mlsanity.com/paper/2205.15263/) (2022)
- [Tree in Tree: from Decision Trees to Decision Graphs](https://mlsanity.com/paper/2110.00392/) (2021)
- [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023)
- [RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space](https://mlsanity.com/paper/2410.16517/) (2024)
- [Can a Single Tree Outperform an Entire Forest?](https://mlsanity.com/paper/2411.17003/) (2024)
- [Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules](https://mlsanity.com/paper/2503.01455/) (2025)
- [Improving the Validity of Decision Trees as Explanations](https://mlsanity.com/paper/2306.06777/) (2023)
- [Correlation and Unintended Biases on Univariate and Multivariate Decision Trees](https://mlsanity.com/paper/2312.01884/) (2023)
- [Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees](https://mlsanity.com/paper/2408.01297/) (2024)
- [Enhance Learning Efficiency of Oblique Decision Tree via Feature Concatenation](https://mlsanity.com/paper/2502.00465/) (2025)
- [Counterfactual Optimal Action Trees (COAT): Interpretable Prescriptive Policies from Observational Data](https://mlsanity.com/paper/2607.14318/) (2026)
- [A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees](https://mlsanity.com/paper/2609.38194/) (2026)

## Abstract (arXiv)

Several recent publications report advances in training optimal decision trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in integer programming and a growing interest in addressing the inherent suboptimality of heuristic approaches such as CART. In this paper, we propose a novel MIP formulation, based on a 1-norm support vector machine model, to train a multivariate ODT for classification problems. We provide cutting plane techniques that tighten the linear relaxation of the MIP formulation, in order to improve run times to reach optimality. Using 36 data-sets from the University of California Irvine Machine Learning Repository, we demonstrate that our formulation outperforms its counterparts in the literature by an average of about 10% in terms of mean out-of-sample testing accuracy across the data-sets. We provide a scalable framework to train multivariate ODT on large data-sets by introducing a novel linear programming (LP) based data selection method to choose a subset of the data for training. Our method is able to routinely handle large data-sets with more than 7,000 sample points and outperform heuristics methods and other MIP based techniques. We present results on data-sets containing up to 245,000 samples. Existing MIP-based methods do not scale well on training data-sets beyond 5,500 samples.