# A Mathematical Programming Approach to Optimal Classification Forests

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 18 Nov 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [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)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Optimization of Tree Ensembles](https://mlsanity.com/paper/1705.10883/) (2017)
- [Computing Optimal Decision Sets with SAT](https://mlsanity.com/paper/2007.15140/) (2020)
- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Robust Optimal Classification Trees under Noisy Labels](https://mlsanity.com/paper/2012.08560/) (2020)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)

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

- [Optimal probabilistic feature shifts for reclassification in tree ensembles](https://mlsanity.com/paper/2412.03722/) (2024)
- [A Unified Optimization Framework for Multiclass Classification with Structured Hyperplane Arrangements](https://mlsanity.com/paper/2510.05047/) (2025)

## Abstract (arXiv)

This paper introduces Weighted Optimal Classification Forests (WOCFs), a new family of classifiers that takes advantage of an optimal ensemble of decision trees to derive accurate and interpretable classifiers. We propose a novel mathematical optimization-based methodology which simultaneously constructs a given number of trees, each of them providing a predicted class for the observations in the feature space. The classification rule is derived by assigning to each observation its most frequently predicted class among the trees. We provide a mixed integer linear programming formulation (MIP) for the problem and several novel MIP strengthening / scaling techniques. We report the results of our computational experiments, from which we conclude that our method has equal or superior performance compared with state-of-the-art tree-based classification methods for small to medium-sized instances. We also present three real-world case studies showing that our methodology has very interesting implications in terms of interpretability. Overall, WOCFs complement existing methods such as CART, Optimal Classification Trees, Random Forests and XGBoost. In addition to its Pareto improvement on accuracy and interpretability, we also see unique properties emerging in terms of different trees focusing on different feature variables. This provides nontrivial improvement in interpretability and usability of the trained model in terms of counterfactual explanation. Thus, despite the apparent computational challenge of WOCFs that limit the size of the problems that can be efficiently solved with current MIP, this is an important research direction that can lead to qualitatively different insights for researchers and complement the toolbox of practitioners for high stakes problems.