Preprint · 2020 · Open access

A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees

Haoran Zhu, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, Jayant Kalagnanam

arXiv (Cornell University), 33, 1771–1781 · Published 6 November 2020 · DOI 10.48550/arxiv.2011.03375

Open PDFView at the publisherCite this paper

In brief

“A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees” is a 2020 preprint by Haoran Zhu and 4 co-authors, published in arXiv (Cornell University). OpenAlex counts 59 citations as of 21 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
59
Most cited in
2023 (14)
References
23
Authors
5

Abstract

Several recent publications report advances in training optimal decision trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in integer programming and a growing interest in addressing the inherent suboptimality of heuristic approaches such as CART. In this paper, we propose a novel MIP formulation, based on a 1-norm support vector machine model, to train a multivariate ODT for classification problems. We provide cutting plane techniques that tighten the linear relaxation of the MIP formulation, in order to improve run times to reach optimality. Using 36 data-sets from the University of California Irvine Machine Learning Repository, we demonstrate that our formulation outperforms its counterparts in the literature by an average of about 10% in terms of mean out-of-sample testing accuracy across the data-sets. We provide a scalable framework to train multivariate ODT on large data-sets by introducing a novel linear programming (LP) based data selection method to choose a subset of the data for training. Our method is able to routinely handle large data-sets with more than 7,000 sample points and outperform heuristics methods and other MIP based techniques. We present results on data-sets containing up to 245,000 samples. Existing MIP-based methods do not scale well on training data-sets beyond 5,500 samples.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Zhu, H., Murali, P., Phan, D. T., Nguyen, L. M., & Kalagnanam, J. (2020). A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees. arXiv (Cornell University), 33, 1771–1781. https://doi.org/10.48550/arxiv.2011.03375

MLA 9

Zhu, Haoran, et al. “A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees.” arXiv (Cornell University), vol. 33, 2020, pp. 1771–1781. https://doi.org/10.48550/arxiv.2011.03375.

Chicago

Zhu, Haoran, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, and Jayant Kalagnanam. 2020. “A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees.” arXiv (Cornell University) 33: 1771–1781. https://doi.org/10.48550/arxiv.2011.03375.

Harvard

Zhu, H. et al. (2020) ‘A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees’, arXiv (Cornell University), 33, pp. 1771–1781. doi:10.48550/arxiv.2011.03375.

IEEE

H. Zhu, P. Murali, D. T. Phan, L. M. Nguyen, and J. Kalagnanam, “A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees,” arXiv (Cornell University), vol. 33, pp. 1771–1781, 2020, doi: 10.48550/arxiv.2011.03375.

BibTeX

@misc{zhu2020scalable,
  title     = {{A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees}},
  author    = {Zhu, Haoran and Murali, Pavankumar and Phan, Dzung T. and Nguyen, Lam M. and Kalagnanam, Jayant},
  howpublished = {arXiv (Cornell University)},
  year      = {2020},
  volume    = {33},
  pages     = {1771--1781},
  doi       = {10.48550/arxiv.2011.03375},
  url       = {https://doi.org/10.48550/arxiv.2011.03375}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202022
202155
202299
20231414
20241313
202577
202699

Topic and keywords

Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications

  • optimal decision trees
  • multivariate decision trees
  • mixed integer programming
  • cutting planes
  • linear programming relaxation
  • data selection
  • large-scale classification

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Zhu, H., Murali, P., Phan, D. T., Nguyen, L. M., & Kalagnanam, J. (2020). A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees. arXiv (Cornell University), 33, 1771–1781. https://doi.org/10.48550/arxiv.2011.03375

How many times has this paper been cited?

59 times, according to OpenAlex on 21 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Haoran Zhu, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, Jayant Kalagnanam.

What is the DOI of this paper?

10.48550/arxiv.2011.03375, permanently at https://doi.org/10.48550/arxiv.2011.03375. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 21 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.