# An improved column-generation-based matheuristic for learning classification trees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 28 references that are in the map.
- First posted on arXiv 22 Aug 2023.

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

- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [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, 4 of 4)

- [Adaptive Optimization for Prediction with Missing Data](https://mlsanity.com/paper/2402.01543/) (2024)
- [Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach](https://mlsanity.com/paper/2602.02173/) (2026)
- [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 highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal trees in terms of accuracy. Other discrete optimization models in the literature address the optimality problem but only work well on relatively small datasets. citefirat2020column proposed a column-generation-based heuristic approach for learning decision trees. This approach improves scalability and can work with large datasets. In this paper, we describe improvements to this column generation approach. First, we modify the subproblem model to significantly reduce the number of subproblems in multiclass classification instances. Next, we show that the data-dependent constraints in the master problem are implied, and use them as cutting planes. Furthermore, we describe a separation model to generate data points for which the linear programming relaxation solution violates their corresponding constraints. We conclude by presenting computational results that show that these modifications result in better scalability.