# MLIC: A MaxSAT-Based framework for learning interpretable classification rules

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2018.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Efficient Exploration of the Rashomon Set of Rule Set Models](https://mlsanity.com/paper/2406.03059/) (2024)
- [Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation](https://mlsanity.com/paper/2202.03888/) (2022)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Efficient Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2205.06936/) (2022)
- [Rule Generation for Classification: Scalability, Interpretability, and Fairness](https://mlsanity.com/paper/2104.10751/) (2021)
- [DeepSaDe: Learning Neural Networks that Guarantee Domain Constraint Satisfaction](https://mlsanity.com/paper/2303.01141/) (2023)
- [SaDe: Learning Models that Provably Satisfy Domain Constraints](https://mlsanity.com/paper/2112.00552/) (2021)
- [Explainable AI using expressive Boolean formulas](https://mlsanity.com/paper/2306.03976/) (2023)
- [Certifying Pareto-Optimality in Multi-Objective Maximum Satisfiability](https://mlsanity.com/paper/2501.17493/) (2025)
- [Reasoning in Neurosymbolic AI](https://mlsanity.com/paper/2505.20313/) (2025)
- [An Incremental MaxSAT-based Model to Learn Interpretable and Balanced Classification Rules](https://mlsanity.com/paper/2403.16418/) (2024)

## Abstract (arXiv)

The wide adoption of machine learning approaches in the industry, government, medicine and science has renewed the interest in interpretable machine learning: many decisions are too important to be delegated to black-box techniques such as deep neural networks or kernel SVMs. Historically, problems of learning interpretable classifiers, including classification rules or decision trees, have been approached by greedy heuristic methods as essentially all the exact optimization formulations are NP-hard. Our primary contribution is a MaxSAT-based framework, called MLIC, which allows principled search for interpretable classification rules expressible in propositional logic. Our approach benefits from the revolutionary advances in the constraint satisfaction community to solve large-scale instances of such problems. In experimental evaluations over a collection of benchmarks arising from practical scenarios, we demonstrate its effectiveness: we show that the formulation can solve large classification problems with tens or hundreds of thousands of examples and thousands of features, and to provide a tunable balance of accuracy vs. interpretability. Furthermore, we show that in many problems interpretability can be obtained at only a minor cost in accuracy. The primary objective of the paper is to show that recent advances in the MaxSAT literature make it realistic to find optimal (or very high quality near-optimal) solutions to large-scale classification problems. The key goal of the paper is to excite researchers in both interpretable classification and in the CP community to take it further and propose richer formulations, and to develop bespoke solvers attuned to the problem of interpretable ML.