{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:42:19Z","timestamp":1773931339371,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031080104","type":"print"},{"value":"9783031080111","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-08011-1_7","type":"book-chapter","created":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T16:16:42Z","timestamp":1654791402000},"page":"74-90","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Shattering Inequalities for\u00a0Learning Optimal Decision Trees"],"prefix":"10.1007","author":[{"given":"Justin J.","family":"Boutilier","sequence":"first","affiliation":[]},{"given":"Carla","family":"Michini","sequence":"additional","affiliation":[]},{"given":"Zachary","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Aghaei, S., Azizi, M.J., Vayanos, P.: Learning optimal and fair decision trees for non-discriminative decision-making (2019)","DOI":"10.1609\/aaai.v33i01.33011418"},{"key":"7_CR2","unstructured":"Aghaei, S., Gomez, A., Vayanos, P.: Learning optimal classification trees: strong max-flow formulations (2020)"},{"issue":"04","key":"7_CR3","first-page":"3146","volume":"34","author":"G Aglin","year":"2020","unstructured":"Aglin, G., Nijssen, S., Schaus, P.: Learning optimal decision trees using caching branch-and-bound search. Proc. AAAI Conf. Artif. Intell. 34(04), 3146\u20133153 (2020)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Aglin, G., Nijssen, S., Schaus, P.: 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, demos (2020)","DOI":"10.24963\/ijcai.2020\/750"},{"issue":"04","key":"7_CR5","first-page":"3195","volume":"34","author":"F Avellaneda","year":"2020","unstructured":"Avellaneda, F.: Efficient inference of optimal decision trees. Proc. AAAI Conf. Artif. Intell. 34(04), 3195\u20133202 (2020)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"JF Benders","year":"1962","unstructured":"Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238\u2013252 (1962)","journal-title":"Numer. Math."},{"issue":"7","key":"7_CR7","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1007\/s10994-017-5633-9","volume":"106","author":"D Bertsimas","year":"2017","unstructured":"Bertsimas, D., Dunn, J.: Optimal classification trees. Mach. Learn. 106(7), 1039\u20131082 (2017). https:\/\/doi.org\/10.1007\/s10994-017-5633-9","journal-title":"Mach. Learn."},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman, L.: Random forests. Mach. Learn. 45(1), 5\u201332 (2001). https:\/\/doi.org\/10.1023\/A:1010933404324","journal-title":"Mach. Learn."},{"key":"7_CR9","volume-title":"Classification and Regression Trees","author":"L Breiman","year":"1984","unstructured":"Breiman, L., Friedman, J., Stone, C.J., Olshen, R.A.: Classification and Regression Trees. CRC Press, Boca Raton (1984)"},{"issue":"4","key":"7_CR10","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.: Combinatorial benders\u2019 cuts for mixed-integer linear programming. Oper. Res. 54(4), 756\u2013766 (2006)","journal-title":"Oper. Res."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G.: Combinatorial optimization: packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (2001)","DOI":"10.1137\/1.9780898717105"},{"key":"7_CR12","unstructured":"Dash, S., G\u00fcnl\u00fck, O., Wei, D.: Boolean decision rules via column generation (2020)"},{"key":"7_CR13","unstructured":"Demirovi\u0107, et al.: Murtree: optimal classification trees via dynamic programming and search (2021)"},{"key":"7_CR14","unstructured":"Dua, D., Graff, C.: UCI machine learning repository (2017). http:\/\/archive.ics.uci.edu\/ml"},{"key":"7_CR15","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.: Identifying minimally infeasible subsystems of inequalities. INFORMS J. Comput. 2, 61\u201363 (1990)","journal-title":"INFORMS J. Comput."},{"key":"7_CR16","unstructured":"Gunluk, O., Kalagnanam, J., Li, M., Menickelly, M., Scheinberg, K.: Optimal generalized decision trees via integer programming (2019)"},{"key":"7_CR17","unstructured":"Gurobi Optimization, L.: Gurobi optimizer reference manual (2021). http:\/\/www.gurobi.com"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Hooker, J., Ottosson, G.: Logic-based benders decomposition. Math. Prog. 96 (2001)","DOI":"10.1007\/s10107-003-0375-9"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Hu, H., Siala, M., Hebrard, E., Huguet, M.J.: 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-20, pp. 1170\u20131176. International Joint Conferences on Artificial Intelligence Organization (2020)","DOI":"10.24963\/ijcai.2020\/163"},{"issue":"1","key":"7_CR20","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.: Constructing optimal binary decision trees is np-complete. Inf. Process. Lett. 5(1), 15\u201317 (1976)","journal-title":"Inf. Process. Lett."},{"key":"7_CR21","unstructured":"Interpretable AI, L.: Interpretable ai documentation (2021). https:\/\/www.interpretable.ai"},{"key":"7_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-030-51825-7_35","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2020","author":"M Janota","year":"2020","unstructured":"Janota, M., Morgado, A.: SAT-based encodings for optimal decision trees with explicit paths. In: Pulina, L., Seidl, M. (eds.) SAT 2020. LNCS, vol. 12178, pp. 501\u2013518. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51825-7_35"},{"issue":"3","key":"7_CR23","first-page":"18","volume":"2","author":"A Liaw","year":"2002","unstructured":"Liaw, A., Wiener, M., et al.: Classification and regression by randomforest. R News 2(3), 18\u201322 (2002)","journal-title":"R News"},{"key":"7_CR24","unstructured":"Lin, J., Zhong, C., Hu, D., Rudin, C., Seltzer, M.: Generalized and scalable optimal sparse decision trees. In: International Conference on Machine Learning, pp. 6150\u20136160. PMLR (2020)"},{"key":"7_CR25","unstructured":"Lin, J.J., Zhong, C., Hu, D., Rudin, C., Seltzer, M.I.: Generalized and scalable optimal sparse decision trees. In: ICML (2020)"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J.: Learning optimal decision trees with sat. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 1362\u20131368. International Joint Conferences on Artificial Intelligence Organization (2018)","DOI":"10.24963\/ijcai.2018\/189"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Nijssen, S., Fromont, E.: Mining optimal decision trees from itemset lattices. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 530\u2013539. KDD 2007, Association for Computing Machinery, New York (2007)","DOI":"10.1145\/1281192.1281250"},{"issue":"1","key":"7_CR28","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF00116251","volume":"1","author":"JR Quinlan","year":"1986","unstructured":"Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81\u2013106 (1986)","journal-title":"Mach. Learn."},{"issue":"5","key":"7_CR29","first-page":"3904","volume":"35","author":"A Schidler","year":"2021","unstructured":"Schidler, A., Szeider, S.: Sat-based decision tree learning for large data sets. Proc. AAAI Conf. Artif. Intell. 35(5), 3904\u20133912 (2021)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"7_CR30","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)"},{"key":"7_CR31","volume-title":"Statistical Learning Theory","author":"V Vapnik","year":"1998","unstructured":"Vapnik, V.: Statistical Learning Theory. Wiley, New York (1998)"},{"issue":"3","key":"7_CR32","doi-asserted-by":"publisher","first-page":"226","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.: Learning optimal decision trees using constraint programming. Constraints 25(3), 226\u2013250 (2020). https:\/\/doi.org\/10.1007\/s10601-020-09312-3","journal-title":"Constraints"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.G., Schaus, P.: 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 (2020)","DOI":"10.24963\/ijcai.2020\/662"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Verwer, S., Zhang, Y.: 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. 27 Jan 2019\u201401 Feb 2019. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33011624"},{"key":"7_CR35","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.: Learning decision trees with flexible constraints and objectives using integer optimization. In: Salvagnin, D., Lombardi, M. (eds.) Integration of AI and OR Techniques in Constraint Programming, pp. 94\u2013103. Springer International Publishing, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-59776-8_8"},{"key":"7_CR36","series-title":"Wiley Series in Discrete Mathematics and Optimization","volume-title":"Integer Programming","author":"L Wolsey","year":"1998","unstructured":"Wolsey, L.: Integer Programming. Wiley Series in Discrete Mathematics and Optimization, Wiley, Hoboken (1998)"},{"key":"7_CR37","unstructured":"Zhu, H., Murali, P., Phan, D.T., Nguyen, L.M., Kalagnanam, J.: 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 6\u201312 December 2020, virtual (2020)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-08011-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T13:03:16Z","timestamp":1667912596000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-08011-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031080104","9783031080111"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-08011-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"10 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Los Angeles, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/usc.edu\/cpaior-2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}