Conference paper · 2023 · Open access
Scalable Optimal Multiway-Split Decision Trees with Constraints
Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), 9891–9899 · Published 26 June 2023 · DOI 10.1609/aaai.v37i8.26180
In brief
“Scalable Optimal Multiway-Split Decision Trees with Constraints” is a 2023 conference paper by Shivaram Subramanian and Wei Sun, published in Proceedings of the AAAI Conference on Artificial Intelligence. OpenAlex counts 12 citations as of 21 November 2026. It is open access: the full text is free to read at Proceedings of the AAAI Conference on Artificial Intelligence.
- Citations
- 12
- Most cited in
- 2026 (8)
- Field-weighted impact
- 1.66
- References
- 37
- Authors
- 2
Abstract
There has been a surge of interest in learning optimal decision trees using mixed-integer programs (MIP) in recent years, as heuristic-based methods do not guarantee optimality and find it challenging to incorporate constraints that are critical for many practical applications. However, existing MIP methods that build on an arc-based formulation do not scale well as the number of binary variables is in the order of 2 to the power of the depth of the tree and the size of the dataset. Moreover, they can only handle sample-level constraints and linear metrics. In this paper, we propose a novel path-based MIP formulation where the number of decision variables is independent of dataset size. We present a scalable column generation framework to solve the MIP. Our framework produces a multiway-split tree which is more interpretable than the typical binary-split trees due to its shorter rules. Our framework is more general as it can handle nonlinear metrics such as F1 score, and incorporate a broader class of constraints. We demonstrate its efficacy with extensive experiments. We present results on datasets containing up to 1,008,372 samples while existing MIP-based decision tree models do not scale well on data beyond a few thousand points. We report superior or competitive results compared to the state-of-art MIP-based methods with up to a 24X reduction in runtime.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Subramanian, S., & Sun, W. (2023). Scalable Optimal Multiway-Split Decision Trees with Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), 9891–9899. https://doi.org/10.1609/aaai.v37i8.26180
MLA 9
Subramanian, Shivaram, and Wei Sun. “Scalable Optimal Multiway-Split Decision Trees with Constraints.” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, 2023, pp. 9891–9899. https://doi.org/10.1609/aaai.v37i8.26180.
Chicago
Subramanian, Shivaram and Wei Sun. 2023. “Scalable Optimal Multiway-Split Decision Trees with Constraints.” Proceedings of the AAAI Conference on Artificial Intelligence 37 (8): 9891–9899. https://doi.org/10.1609/aaai.v37i8.26180.
Harvard
Subramanian, S. and Sun, W. (2023) ‘Scalable Optimal Multiway-Split Decision Trees with Constraints’, Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), pp. 9891–9899. doi:10.1609/aaai.v37i8.26180.
IEEE
S. Subramanian and W. Sun, “Scalable Optimal Multiway-Split Decision Trees with Constraints,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, pp. 9891–9899, 2023, doi: 10.1609/aaai.v37i8.26180.
BibTeX
@inproceedings{subramanian2023scalable,
title = {{Scalable Optimal Multiway-Split Decision Trees with Constraints}},
author = {Subramanian, Shivaram and Sun, Wei},
booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2023},
volume = {37},
number = {8},
pages = {9891--9899},
doi = {10.1609/aaai.v37i8.26180},
url = {https://doi.org/10.1609/aaai.v37i8.26180}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2023 | 1 | |
| 2024 | 2 | |
| 2025 | 1 | |
| 2026 | 8 |
Its field-weighted citation impact is 1.66: it has been cited 1.66 times as often as the average work of the same field, type and year (1.00 is the world average).
Topic and keywords
Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- optimal decision trees
- mixed integer programming
- column generation
- scalability
- F1 score
- interpretable rules
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Subramanian, S., & Sun, W. (2023). Scalable Optimal Multiway-Split Decision Trees with Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), 9891–9899. https://doi.org/10.1609/aaai.v37i8.26180
How many times has this paper been cited?
12 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 Proceedings of the AAAI Conference on Artificial Intelligence: sign in and open the PDF from this page.
Who wrote this paper?
Shivaram Subramanian, Wei Sun.
What is the DOI of this paper?
10.1609/aaai.v37i8.26180, permanently at https://doi.org/10.1609/aaai.v37i8.26180. 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.