# Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 23 Jun 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [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)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [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)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [An Optimization Approach to Learning Falling Rule Lists](https://mlsanity.com/paper/1710.02572/) (2017)

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

- [Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2405.14956/) (2024)
- [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Fast hyperboloid decision tree algorithms](https://mlsanity.com/paper/2310.13841/) (2023)
- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [Anytime Optimal Decision Tree Learning with Continuous Features](https://mlsanity.com/paper/2601.14765/) (2026)
- [Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules](https://mlsanity.com/paper/2503.01455/) (2025)
- [Towards the Formalization of a Trustworthy AI for Mining Interpretable Models explOiting Sophisticated Algorithms](https://mlsanity.com/paper/2510.20621/) (2025)
- [Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach](https://mlsanity.com/paper/2602.02173/) (2026)
- [Improving the Validity of Decision Trees as Explanations](https://mlsanity.com/paper/2306.06777/) (2023)
- [BackboneLearn: A Library for Scaling Mixed-Integer Optimization-Based Machine Learning](https://mlsanity.com/paper/2311.13695/) (2023)
- [Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees](https://mlsanity.com/paper/2408.01297/) (2024)
- [Optimal hypersurface decision trees](https://mlsanity.com/paper/2509.12057/) (2025)
- [Search Strategies for Optimal Classification and Regression Trees](https://mlsanity.com/paper/2607.28170/) (2026)
- [ArborEnum: Decision Tree Rashomon Sets over Continuous Features](https://mlsanity.com/paper/2608.04310/) (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)
- [A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees](https://mlsanity.com/paper/2609.38194/) (2026)

## Abstract (arXiv)

Decision trees are one of the most useful and popular methods in the machine learning toolbox. In this paper, we consider the problem of learning optimal decision trees, a combinatorial optimization problem that is challenging to solve at scale. A common approach in the literature is to use greedy heuristics, which may not be optimal. Recently there has been significant interest in learning optimal decision trees using various approaches (e.g., based on integer programming, dynamic programming) -- to achieve computational scalability, most of these approaches focus on classification tasks with binary features. In this paper, we present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees. Different from existing customized approaches, we consider both regression and classification tasks with continuous features. The basic idea underlying our approach is to split the search space based on the quantiles of the feature distribution -- leading to upper and lower bounds for the underlying optimization problem along the BnB iterations. Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.