# Interpretable and Fair Boolean Rule Sets via Column Generation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 106 references that are in the map.
- First posted on arXiv 16 Nov 2021.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [A Convex Framework for Fair Regression](https://mlsanity.com/paper/1706.02409/) (2017)
- [Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees](https://mlsanity.com/paper/1806.06055/) (2018)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [An Intersectional Definition of Fairness](https://mlsanity.com/paper/1807.08362/) (2018)
- [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)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Scalable Bayesian Rule Lists](https://mlsanity.com/paper/1602.08610/) (2016)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Learning Optimized Risk Scores](https://mlsanity.com/paper/1610.00168/) (2016)
- [Generalized Linear Rule Models](https://mlsanity.com/paper/1906.01761/) (2019)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [Fairness-aware Classification: Criterion, Convexity, and Bounds](https://mlsanity.com/paper/1809.04737/) (2018)
- [Supersparse Linear Integer Models for Interpretable Classification](https://mlsanity.com/paper/1306.6677/) (2013)
- [Optimal Generalized Decision Trees via Integer Programming](https://mlsanity.com/paper/1612.03225/) (2016)
- [Rule Covering for Interpretation and Boosting](https://mlsanity.com/paper/2007.06379/) (2020)
- [Learning Hash Functions Using Column Generation](https://mlsanity.com/paper/1303.0339/) (2013)
- [Binary Matrix Factorisation via Column Generation](https://mlsanity.com/paper/2011.04457/) (2020)

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

- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [A Critical Survey on Fairness Benefits of Explainable AI](https://mlsanity.com/paper/2310.13007/) (2023)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Explainable AI using expressive Boolean formulas](https://mlsanity.com/paper/2306.03976/) (2023)
- [Bias Detection via Maximum Subgroup Discrepancy](https://mlsanity.com/paper/2502.02221/) (2025)
- [A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming](https://mlsanity.com/paper/2407.00843/) (2024)
- [Understanding Fixed Predictions via Confined Regions](https://mlsanity.com/paper/2502.16380/) (2025)
- [Intersectional Fairness via Mixed-Integer Optimization](https://mlsanity.com/paper/2601.19595/) (2026)
- [Explaining with Greater Support: Weighted Column Sampling Optimization for q-Consistent Summary-Explanations](https://mlsanity.com/paper/2302.04528/) (2023)
- [Optimal Pattern Detection Tree for Symbolic Rule-Based Classification](https://mlsanity.com/paper/2605.14374/) (2026)

## Abstract (arXiv)

This paper considers the learning of Boolean rules in disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. We also consider the fairness setting and extend the formulation to include explicit constraints on two different measures of classification parity: equality of opportunity and equalized odds. Column generation (CG) is used to efficiently search over an exponential number of candidate rules without the need for heuristic rule mining. To handle large data sets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 data sets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate. Compared to other fair and interpretable classifiers, our method is able to find rule sets that meet stricter notions of fairness with a modest trade-off in accuracy.