# RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 27 Oct 2025.

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

- [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)
- [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)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Learning Optimal Classification Trees: Strong Max-Flow Formulations](https://mlsanity.com/paper/2002.09142/) (2020)
- [Optimal Generalized Decision Trees via Integer Programming](https://mlsanity.com/paper/1612.03225/) (2016)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound](https://mlsanity.com/paper/2501.07903/) (2025)
- [MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees](https://mlsanity.com/paper/2309.15312/) (2023)
- [Witty: An Efficient Solver for Computing Minimum-Size Decision Trees](https://mlsanity.com/paper/2412.11954/) (2024)
- [bsnsing: A decision tree induction method based on recursive optimal boolean rule composition](https://mlsanity.com/paper/2205.15263/) (2022)
- [Mixed-Integer Linear Optimization for Semi-Supervised Optimal Classification Trees](https://mlsanity.com/paper/2401.09848/) (2024)
- [Branches: Efficiently Seeking Optimal Sparse Decision Trees with AO*](https://mlsanity.com/paper/2406.02175/) (2024)
- [Experiments with Optimal Model Trees](https://mlsanity.com/paper/2503.12902/) (2025)

## Abstract (arXiv)

Mixed-integer programming (MIP) has emerged as a powerful framework for learning optimal decision trees. Yet, existing MIP approaches for regression tasks are either limited to purely binary features or become computationally intractable when continuous, large-scale data are involved. Naively binarizing continuous features sacrifices global optimality and often yields needlessly deep trees. We recast the optimal regression-tree training as a two-stage optimization problem and propose Reduced-Space Optimal Regression Trees (RS-ORT) - a specialized branch-and-bound (BB) algorithm that branches exclusively on tree-structural variables. This design guarantees the algorithm's convergence and its independence from the number of training samples. Leveraging the model's structure, we introduce several bound tightening techniques - closed-form leaf prediction, empirical threshold discretization, and exact depth-1 subtree parsing - that combine with decomposable upper and lower bounding strategies to accelerate the training. The BB node-wise decomposition enables trivial parallel execution, further alleviating the computational intractability even for million-size datasets. Based on the empirical studies on several regression benchmarks containing both binary and continuous features, RS-ORT also delivers superior training and testing performance than state-of-the-art methods. Notably, on datasets with up to 2,000,000 samples with continuous features, RS-ORT can obtain guaranteed training performance with a simpler tree structure and a better generalization ability in four hours.