Learning optimal classification trees using a binary linear program formulation

Sicco Verwer, Y. Zhang

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

53 Downloads (Pure)


We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
Place of PublicationPalo Alto, California USA
PublisherAAAI Press
ISBN (Print)978-1-57735-809-1
Publication statusPublished - 2019
Event33rd AAAI Conference on Artificial Intelligence - Hawaii, Honolulu, United States
Duration: 27 Jan 20191 Feb 2019
Conference number: 33


Conference33rd AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-19
CountryUnited States
Internet address


  • Machine learning
  • decision tree
  • mathematical optimization

Fingerprint Dive into the research topics of 'Learning optimal classification trees using a binary linear program formulation'. Together they form a unique fingerprint.

Cite this