{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:33:31Z","timestamp":1770492811863,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s10601-020-09312-3","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T18:02:33Z","timestamp":1603994553000},"page":"226-250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["Learning optimal decision trees using constraint programming"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0233-4656","authenticated-orcid":false,"given":"H\u00e9l\u00e8ne","family":"Verhaeghe","sequence":"first","affiliation":[]},{"given":"Siegfried","family":"Nijssen","sequence":"additional","affiliation":[]},{"given":"Gilles","family":"Pesant","sequence":"additional","affiliation":[]},{"given":"Claude-Guy","family":"Quimper","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Schaus","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"key":"9312_CR1","unstructured":"Breiman, L. (1984). Classification and regression trees. Routledge."},{"key":"9312_CR2","doi-asserted-by":"publisher","unstructured":"Quinlan, J.R. (1986). Induction of decision trees. Machine Learning, 1(1), 81\u2013106. https:\/\/doi.org\/10.1023\/A:1022643204877.","DOI":"10.1023\/A:1022643204877"},{"key":"9312_CR3","unstructured":"Quinlan, J.R. (1993). C4.5: programs for machine learning. Morgan Kaufmann."},{"key":"9312_CR4","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"},{"issue":"7","key":"9312_CR5","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. (2017). Optimal classification trees. Machine Learning, 106(7), 1039\u20131082.","journal-title":"Machine Learning"},{"key":"9312_CR6","doi-asserted-by":"publisher","unstructured":"Bessiere, C., Hebrard, E., & O\u2019Sullivan, B. (2009). Minimising decision tree size as combinatorial optimisation. In Gent, I. P. (Ed.) Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, Proceedings, Lecture Notes in Computer Science, (Vol. 5732 pp. 173\u2013187): Springer. https:\/\/doi.org\/10.1007\/978-3-642-04244-7_16.","DOI":"10.1007\/978-3-642-04244-7_16"},{"key":"9312_CR7","doi-asserted-by":"publisher","unstructured":"Narodytska, N., Ignatiev, A., Pereira, F., & Marques-Silva, J. (2018). Learning optimal decision trees with SAT. In Lang, J. (Ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, ijcai.org (pp. 1362\u20131368). https:\/\/doi.org\/10.24963\/ijcai.2018\/189.","DOI":"10.24963\/ijcai.2018\/189"},{"key":"9312_CR8","unstructured":"Nijssen, S., & Fromont, E. (2007). Mining optimal decision trees from itemset lattices, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 530\u2013539): ACM."},{"issue":"1","key":"9312_CR9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10618-010-0174-x","volume":"21","author":"S Nijssen","year":"2010","unstructured":"Nijssen, S., & Fromont, E. (2010). Optimal constraint-based decision tree induction from itemset lattices. Data Min. Knowl. Discov., 21(1), 9\u201351.","journal-title":"Data Min. Knowl. Discov."},{"key":"9312_CR10","doi-asserted-by":"publisher","unstructured":"Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 (pp. 1625\u20131632). Honolulu: AAAI Press. https:\/\/doi.org\/10.1609\/aaai.v33i01.33011624.","DOI":"10.1609\/aaai.v33i01.33011624"},{"key":"9312_CR11","doi-asserted-by":"publisher","unstructured":"Bonfietti, A., Lombardi, M., & Milano, M. (2015). Embedding decision trees and random forests in constraint programming. In Michel, L (Ed.) Integration of AI and OR Techniques in Constraint Programming - 12th International Conference, CPAIOR 2015, Barcelona, Spain, Proceedings, Lecture Notes in Computer Science, (Vol. 9075 pp. 74\u201390): Springer. https:\/\/doi.org\/10.1007\/978-3-319-18008-3_6.","DOI":"10.1007\/978-3-319-18008-3_6"},{"issue":"1","key":"9312_CR12","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. https:\/\/doi.org\/10.1016\/0020-0190(76)90095-8.","journal-title":"Information Processing Letters"},{"issue":"2","key":"9312_CR13","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1006\/inco.1996.0040","volume":"126","author":"T Hancock","year":"1996","unstructured":"Hancock, T., Jiang, T., Li, M., & Tromp, J. (1996). Lower bounds on learning decision lists and trees. Information and Computation, 126(2), 114\u2013122.","journal-title":"Information and Computation"},{"key":"9312_CR14","unstructured":"Schaus, P., Aoga, J.O.R., & Guns, T. (2017). Coversize: a global constraint for frequency-based itemset mining. In International Conference on Principles and Practice of Constraint Programming (pp. 529\u2013546): Springer."},{"key":"9312_CR15","doi-asserted-by":"crossref","unstructured":"Dechter, R., & Mateescu, R. (2004). The impact of AND\/OR search spaces on constraint satisfaction and counting. In Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, Proceedings (pp. 731\u2013736).","DOI":"10.1007\/978-3-540-30201-8_56"},{"key":"9312_CR16","doi-asserted-by":"crossref","unstructured":"Babaki, B., Guns, T., & De Raedt, L. (2017). Stochastic constraint programming with and-or branch-and-bound. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia (pp. 539\u2013545).","DOI":"10.24963\/ijcai.2017\/76"},{"key":"9312_CR17","unstructured":"Rossi, F., Van Beek, P., & Walsh, T. (2006). Handbook of constraint programming. Elsevier."},{"key":"9312_CR18","unstructured":"Laurent Michel, P.S. (2018). MiniCP: A lightweight solver for constraint programming. Available from https:\/\/minicp.bitbucket.io."},{"issue":"2-3","key":"9312_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.artint.2006.11.003","volume":"171","author":"R Dechter","year":"2007","unstructured":"Dechter, R., & Mateescu, R. (2007). And\/or search spaces for graphical models. Artificial intelligence, 171(2-3), 73\u2013106.","journal-title":"Artificial intelligence"},{"key":"9312_CR20","unstructured":"Marinescu, R., & Dechter, R. (2004). And\/or tree search for constraint optimization. In Proceedings of the 6th International Workshop on Preferences and Soft Constraints: Citeseer."},{"key":"9312_CR21","unstructured":"Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., R\u00e9gin, J.-C., & Schaus, P. (2016). Compact-table: efficiently filtering table constraints with reversible sparse bit-sets, International Conference on Principles and Practice of Constraint Programming (pp. 207\u2013223): Springer."},{"key":"9312_CR22","volume-title":"Elements of information theory","author":"TM Cover","year":"2012","unstructured":"Cover, T.M., & Thomas, J.A. (2012). Elements of information theory. New York: Wiley."},{"key":"9312_CR23","unstructured":"OscaR Team. (2012). OscaR: Scala in OR. Available from https:\/\/bitbucket.org\/oscarlib\/oscar."},{"issue":"4","key":"9312_CR24","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1287\/ijoc.1060.0189","volume":"19","author":"E Rothberg","year":"2007","unstructured":"Rothberg, E. (2007). An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing, 19(4), 534\u2013541.","journal-title":"INFORMS Journal on Computing"},{"key":"9312_CR25","unstructured":"Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., & Schaus, P. (2019). Learning optimal decision trees using constraint programming. In Beuls, K., Bogaerts, B., Bontempi, G., Geurts, P., Harley, N., Lebichot, B., Lenaerts, T., Louppe, G., & Eecke, P. V. (Eds.) Proceedings of the 31st Benelux Conference on Artificial Intelligence (BNAIC 2019) and the 28th Belgian Dutch Conference on Machine Learning (Benelearn 2019), Brussels, Belgium, CEUR Workshop Proceedings, Vol. 2491: CEUR-WS.org. http:\/\/ceur-ws.org\/Vol-2491\/abstract109.pdf."},{"key":"9312_CR26","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 Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, Tokyo, Japan.","DOI":"10.24963\/ijcai.2020\/662"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09312-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-020-09312-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09312-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T03:03:50Z","timestamp":1607915030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-020-09312-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":26,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9312"],"URL":"https:\/\/doi.org\/10.1007\/s10601-020-09312-3","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,29]]},"assertion":[{"value":"29 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}