{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T06:49:49Z","timestamp":1775544589790,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA9550-23-1-0487"],"award-info":[{"award-number":["FA9550-23-1-0487"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s10601-023-09367-y","type":"journal-article","created":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T21:28:33Z","timestamp":1703712513000},"page":"549-577","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal multivariate decision trees"],"prefix":"10.1007","volume":"28","author":[{"given":"Justin","family":"Boutilier","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4717-816X","authenticated-orcid":false,"given":"Carla","family":"Michini","sequence":"additional","affiliation":[]},{"given":"Zachary","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,27]]},"reference":[{"key":"9367_CR1","volume-title":"Classification and Regression Trees","author":"L Breiman","year":"1984","unstructured":"Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and Regression Trees. New York: Taylor & Francis."},{"issue":"1","key":"9367_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman, L. (2001). Random forests. Machine learning, 45(1), 5\u201332.","journal-title":"Random forests. Machine learning"},{"issue":"3","key":"9367_CR3","first-page":"18","volume":"2","author":"A Liaw","year":"2002","unstructured":"Liaw, A., Wiener, M., et al. (2002). Classification and regression by randomforest. R news, 2(3), 18\u201322.","journal-title":"R news"},{"issue":"1","key":"9367_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L Hyafil","year":"1976","unstructured":"Hyafil, L., & Rivest, R. L. (1976). Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1), 15\u201317.","journal-title":"Information Processing Letters"},{"key":"9367_CR5","unstructured":"Heath, D.G.(1993). A geometric framework for machine learning. PhD thesis, Johns Hopkins University, USA"},{"issue":"1","key":"9367_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1006\/jcss.1995.1011","volume":"50","author":"KU Hoffgen","year":"1995","unstructured":"Hoffgen, K. U., Simon, H. U., & Vanhorn, K. S. (1995). Robust trainability of single neurons. Journal of Computer and System Sciences, 50(1), 114\u2013125.","journal-title":"Journal of Computer and System Sciences"},{"key":"9367_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1009744630224","volume":"2","author":"SK Murthy","year":"1998","unstructured":"Murthy, S. K. (1998). Automatic construction of decision trees from data: A multi-disciplinary survey. Data Mining and Knowledge Discovery, 2, 345\u2013389.","journal-title":"Data Mining and Knowledge Discovery"},{"issue":"1","key":"9367_CR8","first-page":"81","volume":"1","author":"JR Quinlan","year":"1986","unstructured":"Quinlan, J. R. (1986). Induction of decision trees. Machine learning, 1(1), 81\u2013106.","journal-title":"Induction of decision trees. Machine learning"},{"key":"9367_CR9","doi-asserted-by":"crossref","unstructured":"Bertsimas, D., Dunn, J. (2017). Optimal classification trees. Machine Learning. 106","DOI":"10.1007\/s10994-017-5633-9"},{"key":"9367_CR10","doi-asserted-by":"crossref","unstructured":"Aghaei, S., Azizi, M.J., Vayanos, P. (2019). Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making","DOI":"10.1609\/aaai.v33i01.33011418"},{"key":"9367_CR11","unstructured":"Aghaei, S., G\u00f3mez, A., Vayanos, P. (2021). Strong Optimal Classification Trees. Optimization Online. arXiv:2103.15965"},{"key":"9367_CR12","unstructured":"Aghaei, S., G\u00f3mez, A., Jo, N., Vayanos, P. (2021). Learning Optimal Prescriptive Trees from Observational Data. Optimization Online. https:\/\/optimization-online.org\/?p=17313"},{"key":"9367_CR13","unstructured":"Justin, N., Aghaei, S., G\u00f3mez, A., Vayanos, P. (2022). Optimal robust classification trees. In: The AAAI-22 Workshop on Adversarial Machine Learning and Beyond. https:\/\/openreview.net\/forum?id=HbasA9ysA3"},{"key":"9367_CR14","unstructured":"Jo, N., Aghaei, S., Benson, J., G\u00f3mez, A., Vayanos, P. (2022). Learning optimal fair classification trees. arXiv:2201.09932"},{"key":"9367_CR15","unstructured":"Dash, S., G\u00fcnl\u00fck, O., Wei, D. (2018). Boolean decision rules via column generation. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS\u201918, pp. 4660\u20134670. Curran Associates Inc., Red Hook, NY, USA"},{"key":"9367_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10898-021-01009-y","volume":"81","author":"O G\u00fcnl\u00fck","year":"2021","unstructured":"G\u00fcnl\u00fck, O., Kalagnanam, J., Li, M., Menickelly, M., & Scheinberg, K. (2021). Optimal decision trees for categorical data via integer programming. Journal of Global Optimization, 81, 233\u2013260.","journal-title":"Journal of Global Optimization"},{"key":"9367_CR17","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-319-59776-8_8","volume-title":"Integration of AI and OR Techniques in Constraint Programming","author":"S Verwer","year":"2017","unstructured":"Verwer, S., & Zhang, Y. (2017). Learning decision trees with flexible constraints and objectives using integer optimization. In D. Salvagnin & M. Lombardi (Eds.), Integration of AI and OR Techniques in Constraint Programming (pp. 94\u2013103). Cham: Springer."},{"key":"9367_CR18","doi-asserted-by":"crossref","unstructured":"Verwer, S., Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), pp. 1625\u20131632. AAAI Press. 33rd AAAI Conference on Artificial Intelligence, AAAI-19 ; Conference date: 27\u201301\u20132019 Through 01\u201302\u20132019","DOI":"10.1609\/aaai.v33i01.33011624"},{"key":"9367_CR19","unstructured":"Zhu, H., Murali, P., Phan, D.T., Nguyen, L.M., Kalagnanam, J. (2020). A scalable mip-based method for learning optimal multivariate decision trees. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6\u201312, 2020, Virtual"},{"key":"9367_CR20","volume-title":"Integer Programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L. A. (1998). Integer Programming. Wiley, Hoboken, New Jersey, U.S.: Wiley Series in Discrete Mathematics and Optimization."},{"key":"9367_CR21","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J. (2018). Learning optimal decision trees with SAT. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI\u201918, pp. 1362\u20131368. AAAI Press, Stockholm, Sweden","DOI":"10.24963\/ijcai.2018\/189"},{"issue":"04","key":"9367_CR22","doi-asserted-by":"publisher","first-page":"3195","DOI":"10.1609\/aaai.v34i04.5717","volume":"34","author":"F Avellaneda","year":"2020","unstructured":"Avellaneda, F. (2020). Efficient inference of optimal decision trees. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3195\u20133202.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"9367_CR23","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-030-51825-7_35","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2020","author":"M Janota","year":"2020","unstructured":"Janota, M., & Morgado, A. (2020). SAT-based encodings for optimal decision trees with explicit paths. In L. Pulina & M. Seidl (Eds.), Theory and Applications of Satisfiability Testing - SAT 2020 (pp. 501\u2013518). Cham: Springer."},{"issue":"5","key":"9367_CR24","doi-asserted-by":"publisher","first-page":"3904","DOI":"10.1609\/aaai.v35i5.16509","volume":"35","author":"A Schidler","year":"2021","unstructured":"Schidler, A., & Szeider, S. (2021). SAT-based decision tree learning for large data sets. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3904\u20133912.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"9367_CR25","doi-asserted-by":"crossref","unstructured":"Hu, H., Siala, M., Hebrard, E., Huguet, M.-J. (2020). Learning optimal decision trees with MaxSAT and its integration in adaboost. In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI\u201320, pp. 1170\u20131176. International Joint Conferences on Artificial Intelligence Organization, Yokohama, Japan","DOI":"10.24963\/ijcai.2020\/163"},{"issue":"2","key":"9367_CR26","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/s10601-023-09348-1","volume":"28","author":"P Shati","year":"2023","unstructured":"Shati, P., Cohen, E., & McIlraith, S. A. (2023). SAT-based optimal classification trees for non-binary data. Constraints, 28(2), 166\u2013202.","journal-title":"Constraints"},{"key":"9367_CR27","doi-asserted-by":"crossref","unstructured":"Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., Schaus, P. (2020). Learning optimal decision trees using constraint programming (extended abstract). In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 4765\u20134769. International Joint Conferences on Artificial Intelligence Organization, Yokohama, Japan","DOI":"10.24963\/ijcai.2020\/662"},{"key":"9367_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10601-020-09312-3","volume":"25","author":"H Verhaeghe","year":"2020","unstructured":"Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., & Schaus, P. (2020). Learning optimal decision trees using constraint programming. Constraints, 25, 1\u201325. https:\/\/doi.org\/10.1007\/s10601-020-09312-3","journal-title":"Constraints"},{"key":"9367_CR29","doi-asserted-by":"crossref","unstructured":"Nijssen, S., Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD \u201907, pp. 530\u2013539. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/1281192.1281250"},{"issue":"04","key":"9367_CR30","doi-asserted-by":"publisher","first-page":"3146","DOI":"10.1609\/aaai.v34i04.5711","volume":"34","author":"G Aglin","year":"2020","unstructured":"Aglin, G., Nijssen, S., & Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3146\u20133153.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"9367_CR31","doi-asserted-by":"crossref","unstructured":"Aglin, G., Nijssen, S., Schaus, P. (2020). PyDL8.5: a library for learning optimal decision trees. In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 5222\u20135224. International Joint Conferences on Artificial Intelligence Organization, Yokohama, Japan","DOI":"10.24963\/ijcai.2020\/750"},{"key":"9367_CR32","unstructured":"Lin, J.J., Zhong, C., Hu, D., Rudin, C., Seltzer, M.I. (2020). Generalized and scalable optimal sparse decision trees. In: ICML"},{"key":"9367_CR33","unstructured":"Demirovi\u0107, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., Stuckey, P.J. (2021). MurTree: Optimal Classification Trees via Dynamic Programming and Search"},{"key":"9367_CR34","unstructured":"Mazumder, R., Meng, X., Wang, H. (2022). Quant-BnB: A scalable branch-and-bound method for optimal decision trees with continuous features. In: Proceedings of the 39th International Conference on Machine Learning, PMLP, vol. 162, pp. 15255\u201315277"},{"issue":"1","key":"9367_CR35","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.ejor.2019.12.002","volume":"284","author":"R Blanquero","year":"2020","unstructured":"Blanquero, R., Carrizosa, E., Molero-Ro, C., & Romero Morales, D. (2020). Sparsity in optimal randomized classification trees. European Journal of Operational Research, 284(1), 255\u2013272. https:\/\/doi.org\/10.1016\/j.ejor.2019.12.002","journal-title":"European Journal of Operational Research"},{"key":"9367_CR36","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105281","volume":"132","author":"R Blanquero","year":"2021","unstructured":"Blanquero, R., Carrizosa, E., Molero-Ro, C., & Romero Morales, D. (2021). Optimal randomized classification trees. Computers & Operations Research, 132, 105281. https:\/\/doi.org\/10.1016\/j.cor.2021.105281","journal-title":"Computers & Operations Research"},{"key":"9367_CR37","unstructured":"Lin, J., Zhong, C., Hu, D., Rudin, C., Seltzer, M. (2020). Generalized and scalable optimal sparse decision trees. In: International Conference on Machine Learning, pp. 6150\u20136160. PMLR"},{"issue":"1","key":"9367_CR38","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"JF Benders","year":"1962","unstructured":"Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238\u2013252.","journal-title":"Numerische Mathematik"},{"key":"9367_CR39","unstructured":"Michini, C., Zhou, Z. (2022). A polyhedral study of multivariate decision trees. Optimization Online. https:\/\/optimization-online.org\/?p=20972"},{"key":"9367_CR40","volume-title":"Statistical Learning Theory","author":"V Vapnik","year":"1998","unstructured":"Vapnik, V. (1998). Statistical Learning Theory. Hoboken, New Jersey, U.S.: Wiley."},{"key":"9367_CR41","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G. (2001). Combinatorial Optimization: Packing and Covering. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, United States","DOI":"10.1137\/1.9780898717105"},{"key":"9367_CR42","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., & Tsitsiklis, J. (1997). Introduction to Linear Optimization (1st ed.). Nashua, New Hampshire: Athena Scientific.","edition":"1"},{"key":"9367_CR43","unstructured":"Dantzig, G.B. (1998). Linear Programming and Extensions. A Rand Corporation research study. Princeton University Press, Princeton, New Jersey. http:\/\/books.google.ch\/books?id=2j46uCX5ZAYC"},{"key":"9367_CR44","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/ijoc.2.1.61","volume":"2","author":"J Gleeson","year":"1990","unstructured":"Gleeson, J., & Ryan, J. (1990). Identifying minimally infeasible subsystems of inequalities. INFORMS Journal on Computing, 2, 61\u201363.","journal-title":"INFORMS Journal on Computing"},{"key":"9367_CR45","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of Linear and Integer Programming. Chichester: Wiley."},{"issue":"4","key":"9367_CR46","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/opre.1060.0286","volume":"54","author":"G Codato","year":"2006","unstructured":"Codato, G., & Fischetti, M. (2006). Combinatorial Benders\u2019 cuts for mixed-integer linear programming. Operations Research, 54(4), 756\u2013766.","journal-title":"Operations Research"},{"key":"9367_CR47","doi-asserted-by":"crossref","unstructured":"Hooker, J., Ottosson, G. (2001). Logic-based benders decomposition. Mathematical Programming, 96","DOI":"10.1007\/s10107-003-0375-9"},{"issue":"7","key":"9367_CR48","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1016\/0167-8655(96)00033-5","volume":"17","author":"DE Brown","year":"1996","unstructured":"Brown, D. E., Pittard, C. L., & Park, H. (1996). Classification trees with optimal multivariate decision nodes. Pattern Recognition Letters, 17(7), 699\u2013703. https:\/\/doi.org\/10.1016\/0167-8655(96)00033-5","journal-title":"Pattern Recognition Letters"},{"key":"9367_CR49","doi-asserted-by":"crossref","unstructured":"Murthy, S.K., Kasif, S., Salzberg, S. (1994). A system for induction of oblique decision trees. arXiv:9408103","DOI":"10.1613\/jair.63"},{"key":"9367_CR50","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., & Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825\u20132830.","journal-title":"Journal of Machine Learning Research"},{"key":"9367_CR51","unstructured":"Dua, D., Graff, C. (2017). UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"9367_CR52","unstructured":"Interpretable\u00a0AI, L. (2021). Interpretable AI Documentation. https:\/\/www.interpretable.ai"},{"key":"9367_CR53","unstructured":"Gurobi Optimization, LLC. (2023). Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09367-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09367-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09367-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T09:16:50Z","timestamp":1707470210000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09367-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9367"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09367-y","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"21 November 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant conflicts of interest\/competing interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest\/Competing interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}