# Optimal Decision Diagrams for Classification

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 54 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [Learning Optimal Classification Trees: Strong Max-Flow Formulations](https://mlsanity.com/paper/2002.09142/) (2020)
- [Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms](https://mlsanity.com/paper/2012.12356/) (2020)
- [A New Look at BDDs for Pseudo-Boolean Constraints](https://mlsanity.com/paper/1401.5860/) (2014)
- [Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams](https://mlsanity.com/paper/2009.00481/) (2020)
- [Optimizing Binary Decision Diagrams with MaxSAT for classification](https://mlsanity.com/paper/2203.11386/) (2022)
- [Decision Stream: Cultivating Deep Decision Trees](https://mlsanity.com/paper/1704.07657/) (2017)
- [Large Random Forests: Optimisation for Rapid Evaluation](https://mlsanity.com/paper/1912.10934/) (2019)

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

- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Decision Predicate Graphs: Enhancing Interpretability in Tree Ensembles](https://mlsanity.com/paper/2404.02942/) (2024)
- [Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts](https://mlsanity.com/paper/2207.07690/) (2022)
- [Neural Logic Networks for Interpretable Classification](https://mlsanity.com/paper/2508.08172/) (2025)
- [Explaining Control Policies through Predicate Decision Diagrams](https://mlsanity.com/paper/2503.06420/) (2025)
- [Learning Compact Boolean Networks](https://mlsanity.com/paper/2602.05830/) (2026)
- [Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms](https://mlsanity.com/paper/2605.06561/) (2026)
- [Loss-Optimal Classification Trees: A Generalized Framework and the Logistic Case](https://mlsanity.com/paper/2306.00857/) (2023)
- [CARNA: Characterizing Advanced heart failure Risk and hemodyNAmic phenotypes using learned multi-valued decision diagrams](https://mlsanity.com/paper/2306.06801/) (2023)
- [On Trustworthy Rule-Based Models and Explanations](https://mlsanity.com/paper/2507.07576/) (2025)

## Abstract (arXiv)

Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.