# An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 21 Sep 2026.

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

- [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)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound](https://mlsanity.com/paper/2501.07903/) (2025)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [An improved column-generation-based matheuristic for learning classification trees](https://mlsanity.com/paper/2308.11477/) (2023)
- [Rolling Lookahead Learning for Optimal Classification Trees](https://mlsanity.com/paper/2304.10830/) (2023)

## Abstract (arXiv)

We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal value and recovery of an optimal tree. The reduced model supports two solution methods: column generation and message passing. Column generation solves integral restricted LPs and uses bounds over the full feasible domain to certify optimality. Message passing recursively combines optimal subtree costs. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.