# Scalable Optimal Multiway-Split Decision Trees with Constraints

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 14 Feb 2023.

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

- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Model Distillation for Revenue Optimization: Interpretable Personalized Pricing](https://mlsanity.com/paper/2007.01903/) (2020)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [Optimal Decision Trees for Nonlinear Metrics](https://mlsanity.com/paper/2009.06921/) (2020)
- [Constrained Prescriptive Trees via Column Generation](https://mlsanity.com/paper/2207.10163/) (2022)

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

- [Learning Prescriptive ReLU Networks](https://mlsanity.com/paper/2306.00651/) (2023)
- [Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach](https://mlsanity.com/paper/2602.02173/) (2026)
- [Interpretable clustering via optimal multi-way decision trees](https://mlsanity.com/paper/2602.13586/) (2026)
- [PresAIse, A Prescriptive AI Solution for Enterprises](https://mlsanity.com/paper/2402.02006/) (2024)
- [Empowering Decision Trees via Shape Function Branching](https://mlsanity.com/paper/2510.19040/) (2025)
- [Adaptive Multi-Branching for Shallow Decision Tree Induction](https://mlsanity.com/paper/2608.29262/) (2026)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)
- [Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments](https://mlsanity.com/paper/2609.23308/) (2026)
- [An Exact Junction-Tree Extended Formulation for Optimal Classification Trees](https://mlsanity.com/paper/2609.24741/) (2026)

## Abstract (arXiv)

There has been a surge of interest in learning optimal decision trees using mixed-integer programs (MIP) in recent years, as heuristic-based methods do not guarantee optimality and find it challenging to incorporate constraints that are critical for many practical applications. However, existing MIP methods that build on an arc-based formulation do not scale well as the number of binary variables is in the order of O(2dN), where d and N refer to the depth of the tree and the size of the dataset. Moreover, they can only handle sample-level constraints and linear metrics. In this paper, we propose a novel path-based MIP formulation where the number of decision variables is independent of N. We present a scalable column generation framework to solve the MIP optimally. Our framework produces a multiway-split tree which is more interpretable than the typical binary-split trees due to its shorter rules. Our method can handle nonlinear metrics such as F1 score and incorporate a broader class of constraints. We demonstrate its efficacy with extensive experiments. We present results on datasets containing up to 1,008,372 samples while existing MIP-based decision tree models do not scale well on data beyond a few thousand points. We report superior or competitive results compared to the state-of-art MIP-based methods with up to a 24X reduction in runtime.