Learning optimal decision trees with SAT

Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

27 Citations (Scopus)


Explanations of machine learning (ML) predictions are of fundamental importance in different settings. Moreover, explanations should be succinct, to enable easy understanding by human decision makers. Decision trees represent an often used approach for developing explainable ML models, motivated by the natural mapping between decision tree paths and rules. Clearly, smaller trees translate directly to smaller rules, and so one challenge is to devise solutions for computing smallest size decision trees given training data. Although simple to formulate, the computation of smallest size decision trees turns out to be an extremely challenging computational problem, for which no practical solutions are known. This paper develops a SAT-based model for computing smallest-size decision trees given training data. In sharp contrast with past work, the proposed SAT model is shown to scale for publicly available datasets of practical interest.

Original languageEnglish
Title of host publicationProceedings - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Subtitle of host publicationStockholm, 13-19 July 2018
EditorsJerome Lang
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages7
ISBN (Electronic)9780999241127
Publication statusPublished - 2018
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence 2018 - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018
Conference number: 27th
https://www.ijcai.org/proceedings/2018/ (Proceedings)


ConferenceInternational Joint Conference on Artificial Intelligence 2018
Abbreviated titleIJCAI 2018
Internet address


  • Constraints and SAT
  • SAT
  • Applications
  • Constraints and Data Mining
  • Machine Learning

Cite this