# Tight Mixed-Integer Optimization Formulations for Prescriptive Trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 28 Feb 2023.

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

- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Maximum Resilience of Artificial Neural Networks](https://mlsanity.com/paper/1705.01040/) (2017)
- [Training verified learners with learned verifiers](https://mlsanity.com/paper/1805.10265/) (2018)
- [Mixed-Integer Optimization with Constraint Learning](https://mlsanity.com/paper/2111.04469/) (2021)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [JANOS: An Integrated Predictive and Prescriptive Modeling Framework](https://mlsanity.com/paper/1911.09461/) (2019)
- [Optimization of Tree Ensembles](https://mlsanity.com/paper/1705.10883/) (2017)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded](https://mlsanity.com/paper/1803.00952/) (2018)
- [ENTMOOT: A Framework for Optimization over Ensemble Tree Models](https://mlsanity.com/paper/2003.04774/) (2020)
- [Decision Forest: A Nonparametric Approach to Modeling Irrational Choice](https://mlsanity.com/paper/1904.11532/) (2019)
- [Equivalent and Approximate Transformations of Deep Neural Networks](https://mlsanity.com/paper/1905.11428/) (2019)
- [Learning optimization models in the presence of unknown relations](https://mlsanity.com/paper/1401.1061/) (2014)
- [Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding](https://mlsanity.com/paper/1704.03954/) (2017)
- [Assortment Optimization under the Decision Forest Model](https://mlsanity.com/paper/2103.14067/) (2021)

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

- [A Unified Optimization Framework for Multiclass Classification with Structured Hyperplane Arrangements](https://mlsanity.com/paper/2510.05047/) (2025)

## Abstract (arXiv)

We focus on modeling the relationship between an input feature vector and the predicted outcome of a trained decision tree using mixed-integer optimization. This can be used in many practical applications where a decision tree or tree ensemble is incorporated into an optimization problem to model the predicted outcomes of a decision. We propose tighter mixed-integer optimization formulations than those previously introduced. Existing formulations can be shown to have linear relaxations that have fractional extreme points, even for the simple case of modeling a single decision tree. A formulation we propose, based on a projected union of polyhedra approach, is ideal for a single decision tree. While the formulation is generally not ideal for tree ensembles or if additional constraints are added, it generally has fewer extreme points, leading to a faster time to solve, particularly if the formulation has relatively few trees. However, previous work has shown that formulations based on a binary representation of the feature vector perform well computationally and hence are attractive for use in practical applications. We present multiple approaches to tighten existing formulations with binary vectors, and show that fractional extreme points are removed when there are multiple splits on the same feature. At an extreme, we prove that this results in ideal formulations for tree ensembles modeling a one-dimensional feature vector. Building on this result, we also show via numerical simulations that these additional constraints result in significantly tighter linear relaxations when the feature vector is low dimensional. We also present instances where the time to solve to optimality is significantly improved using these formulations.