{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T22:30:46Z","timestamp":1783809046470,"version":"3.55.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,4,17]],"date-time":"2021-04-17T00:00:00Z","timestamp":1618617600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,17]],"date-time":"2021-04-17T00:00:00Z","timestamp":1618617600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001602","name":"Science Foundation Ireland","doi-asserted-by":"crossref","award":["SFI\/12\/RC\/2289"],"award-info":[{"award-number":["SFI\/12\/RC\/2289"]}],"id":[{"id":"10.13039\/501100001602","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Modeling a combinatorial problem is a hard and error-prone task requiring significant expertise. Constraint acquisition methods attempt to automate this process by learning constraints from examples of solutions and (usually) non-solutions. Active methods query an oracle while passive methods do not. We propose a known but not widely-used application of machine learning to constraint acquisition: training a classifier to discriminate between solutions and non-solutions, then deriving a constraint model from the trained classifier. We discuss a wide range of possible new acquisition methods with useful properties inherited from classifiers. We also show the potential of this approach using a Naive Bayes classifier, obtaining a new passive acquisition algorithm that is considerably faster than existing methods, scalable to large constraint sets, and robust under errors.<\/jats:p>","DOI":"10.1007\/s10472-021-09736-4","type":"journal-article","created":{"date-parts":[[2021,4,17]],"date-time":"2021-04-17T10:03:11Z","timestamp":1618653791000},"page":"655-674","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Classifier-based constraint acquisition"],"prefix":"10.1007","volume":"89","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6218-9158","authenticated-orcid":false,"given":"S. D.","family":"Prestwich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E. C.","family":"Freuder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"O\u2019Sullivan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Browne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,17]]},"reference":[{"key":"9736_CR1","doi-asserted-by":"crossref","unstructured":"Asdi, H.A., Bessiere, C., Ezzahir, R., Lazaar, N.: Time-bounded query generator for constraint acquisition. In: Proceedings of the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, vol. 10848, pp 1\u201317 (2018)","DOI":"10.1007\/978-3-319-93031-2_1"},{"key":"9736_CR2","unstructured":"Arcangioli, R., Bessiere, C., Lazaar, N.: Multiple constraint acquisition. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (2016)"},{"key":"9736_CR3","doi-asserted-by":"crossref","unstructured":"Asafu-Adjei, J.K., Betensky, R.A.: A pairwise Na\u00efve Bayes approach to Bayesian classification. Intern. J. Pattern Recognit. Artif. Intell. 29(7) (2015)","DOI":"10.1142\/S0218001415500238"},{"key":"9736_CR4","doi-asserted-by":"crossref","unstructured":"Bartolini, A., Lombardi, M., Milano, M., Benini, L.: Neuron constraints to model complex real-world problems. In: Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming Lecture Notes in Computer Science, vol. 6876, pp 115\u2013129 (2011)","DOI":"10.1007\/978-3-642-23786-7_11"},{"key":"9736_CR5","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., Simonis, H.: Modelseeker: Extracting global constraint models from positive examples. In: Data Mining and Constraint Programming, Lecture Notes in Computer Science, vol. 10101, pp 77\u201395. Springer (2016)","DOI":"10.1007\/978-3-319-50137-6_4"},{"key":"9736_CR6","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.artint.2015.08.001","volume":"244","author":"C Bessiere","year":"2017","unstructured":"Bessiere, C., Koriche, F., Lazaara, N., O\u2019Sullivan, B.: Constraint acquisition. Artif. Intell. 244, 315\u2013342 (2017)","journal-title":"Artif. Intell."},{"key":"9736_CR7","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Coletta, R., Freuder, E.C., O\u2019Sullivan, B.: Leveraging the learning power of examples in automated constraint acquisition. In: Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming Lecture Notes in Computer Science, vol. 3258, pp 123\u2013137 (2004)","DOI":"10.1007\/978-3-540-30201-8_12"},{"key":"9736_CR8","unstructured":"Bessiere, C., Coletta, R., Daoudi, A., Lazaar, N., Bouyakhf, E.H.: Boosting constraint acquisition via generalization queries. In: Proceedings of the 21st European Conference on Artificial Intelligence, pp 99\u2013104 (2014)"},{"key":"9736_CR9","unstructured":"Bessiere, C., Coletta, R., Hebrard, E., Katsirelos, G., Lazaar, N., Narodytska, N., Quimper, C.-G., Walsh, T.: Constraint acquisition via partial queries. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pp 475\u2013481. AAAI Press (2013)"},{"key":"9736_CR10","doi-asserted-by":"crossref","unstructured":"Bonfietti, A., Lombardi, M., Milano, M.: Embedding decision trees and random forests in constraint programming. In: Proceedings of the International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, vol. 9075, pp 74\u201390. Springer (2015)","DOI":"10.1007\/978-3-319-18008-3_6"},{"key":"9736_CR11","doi-asserted-by":"crossref","unstructured":"Browne, D., Giering, M., Prestwich, S.D.: Pulse-net: Dynamic compression of convolutional neural networks. In: Proceedings of the IEEE 5th World Forum on Internet of Things (2019)","DOI":"10.1109\/WF-IoT.2019.8767300"},{"key":"9736_CR12","doi-asserted-by":"crossref","unstructured":"Casale, P., Pujol, O., Radeva, P.: Approximate convex hulls family for One-Class classification. In: proceedings of the International Workshop on Multiple Classifier Systems Lecture in Notes Computer Sci, vol. 6713, pp 106\u2013115 (2011)","DOI":"10.1007\/978-3-642-21557-5_13"},{"key":"9736_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1023\/A:1009894810205","volume":"4","author":"BMW Cheng","year":"1999","unstructured":"Cheng, B.M.W., Choi, K.M.F., Lee, H.H.M., Wu, J.C.K.: Increasing constraint propagation by redundant modeling: An experience report. Constraints 4, 167\u2013192 (1999)","journal-title":"Constraints"},{"key":"9736_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1023\/A:1007413511361","volume":"29","author":"P Domingos","year":"1997","unstructured":"Domingos, P., Pazzani, M.: On the optimality of the simple bayesian classifier under Zero-One loss. Mach. Learn. 29, 103\u2013130 (1997)","journal-title":"Mach. Learn."},{"issue":"3","key":"9736_CR15","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/s10601-018-9285-6","volume":"23","author":"M Fischetti","year":"2018","unstructured":"Fischetti, M., Jo, J.: Deep neural networks as 0-1 mixed integer linear programs: A feasibility study. Constraints 23(3), 296\u2013309 (2018)","journal-title":"Constraints"},{"key":"9736_CR16","unstructured":"Frankle, J., Carbin, M.: The lottery ticket hypothesis: Finding sparse, trainable neural networks. In: Proceedings of the International Conference on Learning Representations. to appear (2019)"},{"key":"9736_CR17","unstructured":"Freuder, E.C.: Constraints: The ties that bind. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp 1520\u20131523. AAAI Press (2006)"},{"key":"9736_CR18","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s10601-017-9275-0","volume":"23","author":"EC Freuder","year":"2018","unstructured":"Freuder, E.C.: Progress towards the holy grail. Constraints 23, 158\u2013171 (2018)","journal-title":"Constraints"},{"issue":"1","key":"9736_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0218213002000769","volume":"11","author":"EC Freuder","year":"2002","unstructured":"Freuder, E.C., Wallace, R.J.: Suggestion strategies for Constraint-Based matchmaker agents. Int. J. Artif. Intell. Tools 11(1), 3\u201318 (2002)","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"9736_CR20","volume-title":"Handbook of Constraint Programming","author":"IP Gent","year":"2006","unstructured":"Gent, I.P., Petrie, K.E., Puget, J.-F.: Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"issue":"2","key":"9736_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1080\/00949650008812016","volume":"66","author":"IJ Good","year":"2000","unstructured":"Good, I.J.: Turing\u2019s anticipation of empirical Bayes in connection with the cryptanalysis of the naval enigma. J. Stat. Comput. Simul. 66(2), 101\u2013111 (2000)","journal-title":"J. Stat. Comput. Simul."},{"issue":"3","key":"9736_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10601-006-7094-9","volume":"11","author":"B Hnich","year":"2006","unstructured":"Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test problem. Constraints 11(3), 199\u2013219 (2006)","journal-title":"Constraints"},{"issue":"430","key":"9736_CR23","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1080\/01621459.1995.10476572","volume":"90","author":"RE Kass","year":"1995","unstructured":"Kass, R.E., Raftery, A.E.: Bayes Factors. J. Amer. Stat. Assoc. 90(430), 773\u2013795 (1995)","journal-title":"J. Amer. Stat. Assoc."},{"issue":"3","key":"9736_CR24","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1017\/S026988891300043X","volume":"29","author":"S Khan","year":"2014","unstructured":"Khan, S., Madden, M.: One-Class Classification: Taxonomy of study and review of techniques. Knowl. Eng. Rev. 29(3), 345\u2013374 (2014)","journal-title":"Knowl. Eng. Rev."},{"key":"9736_CR25","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1007\/s10994-017-5640-x","volume":"106","author":"S Kolb","year":"2017","unstructured":"Kolb, S., Paramonov, S., Guns, T., De Raedt, L.: Learning constraints in spreadsheets and tabular data. Mach. Learn. 106, 1441\u20131468 (2017)","journal-title":"Mach. Learn."},{"key":"9736_CR26","doi-asserted-by":"crossref","unstructured":"Lallouet, A., Lopez, M., Martin, L., Vrain, C.: On learning constraint problems. In: Proceedings of the IEEE International Conference on Tools With Artificial Intelligence, pp 45\u201352 (2010)","DOI":"10.1109\/ICTAI.2010.16"},{"key":"9736_CR27","doi-asserted-by":"crossref","unstructured":"Lallouet, A., Legtchenko, A.: Two contributions of constraint programming to machine learning. In: Proceedings of the European Conference on Machine Learning Lecture Notes in Artificial Intelligence, vol. 3720, pp 617\u2013624. Springer (2005)","DOI":"10.1007\/11564096_61"},{"key":"9736_CR28","doi-asserted-by":"crossref","unstructured":"Lombardi, M., Milano, M.: Boosting combinatorial problem modeling with machine learning. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp 5472\u20135478 (2018)","DOI":"10.24963\/ijcai.2018\/772"},{"issue":"Supplement C","key":"9736_CR29","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.artint.2016.01.005","volume":"244","author":"M Lombardi","year":"2017","unstructured":"Lombardi, M., Milano, M., Bartolini, A.: Empirical decision model learning. Artif. Intell. 244(Supplement C), 343\u2013367 (2017)","journal-title":"Artif. Intell."},{"key":"9736_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to information retrieval","author":"CD Manning","year":"2008","unstructured":"Manning, C.D., Raghavan, P., Sch\u00fctze, M.: Introduction to information retrieval. Cambridge University Press, Cambridge (2008)"},{"key":"9736_CR31","unstructured":"Prestwich, S.D.: Robust constraint acquisition by sequential analysis. In: Proceedings of the 24th European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 325, pp 355\u2013362. IOS Press (2020)"},{"key":"9736_CR32","doi-asserted-by":"crossref","unstructured":"O\u2019Sullivan, B.: Automated modelling and solving in constraint programming. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp 1493\u20131497 (2010)","DOI":"10.1609\/aaai.v24i1.7530"},{"issue":"3","key":"9736_CR33","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1016\/j.ejor.2017.02.034","volume":"261","author":"TP Pawlak","year":"2017","unstructured":"Pawlak, T.P., Krawiec, K.: Automatic synthesis of constraints from examples using mixed integer linear programming. Eur. J. Oper. Res. 261(3), 1141\u20131157 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"9736_CR34","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1007361123060","volume":"26","author":"L De Raedt","year":"1997","unstructured":"De Raedt, L., Dehaspe, L.: Clausal discovery. Mach. Learn. 26, 99\u2013146 (1997)","journal-title":"Mach. Learn."},{"key":"9736_CR35","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0004-3702(94)90112-0","volume":"70","author":"L De Raedt","year":"1994","unstructured":"De Raedt, L., Dz\u0306eroski, S.: First Order jk-clausal Theories are PAC-learnable. Artif. Intell. 70, 375\u2013392 (1994)","journal-title":"Artif. Intell."},{"key":"9736_CR36","doi-asserted-by":"crossref","unstructured":"De Raedt, L., Passerini, A., Reso, S.: Learning constraints from examples. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp 7965\u20137970 (2018)","DOI":"10.1609\/aaai.v32i1.12217"},{"key":"9736_CR37","doi-asserted-by":"crossref","unstructured":"Say, B., Wu, G., Zhou, Y.Q., Sanner, S.: Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programs. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp 750\u2013756 (2017)","DOI":"10.24963\/ijcai.2017\/104"},{"key":"9736_CR38","unstructured":"Smith, B.M., Stergiou, K., Walsh, T.: Modelling the Golomb Ruler Problem. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (1999)"},{"key":"9736_CR39","unstructured":"Snell, J., Swersky, K., Zemel, R.: Prototypical networks for few-shot learning. In: Proceedings of the 31st Conference on Neural Information Processing Systems (2017)"},{"key":"9736_CR40","unstructured":"Tjeng, V., Tedrake, R.: Verifying neural networks with mixed integer programming. coRR (2017)"},{"key":"9736_CR41","doi-asserted-by":"crossref","unstructured":"Tseitin, G.: On the complexity of derivation in propositional calculus. In: Siekmann, J., Wrightson, G. (eds.) Automation of Reasoning: Classical Papers in Computational Logic, vol. 2, pp 466\u2013483. Springer (1983)","DOI":"10.1007\/978-3-642-81955-1_28"},{"key":"9736_CR42","doi-asserted-by":"crossref","unstructured":"Tsouros, D.C., Stergiou, K., Sarigiannidis, P.G.: Efficient methods for constraint acquisition. In: Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol. 11008, pp 373\u2013388 (2018)","DOI":"10.1007\/978-3-319-98334-9_25"},{"key":"9736_CR43","doi-asserted-by":"crossref","unstructured":"Tsouros, D.C., Stergiou, K., Bessiere, C.: Structure-driven multiple constraint acquisition. In: 25th International Conference on Principles and Practice of Constraint Programming Lecture Notes in Computer Science, vol. 11802, pp 709\u2013725 (2019)","DOI":"10.1007\/978-3-030-30048-7_41"},{"issue":"11","key":"9736_CR44","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"9736_CR45","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.artint.2015.05.004","volume":"244","author":"S Verwer","year":"2017","unstructured":"Verwer, S., Zhang, Y., Ye, Q.C.: Auction optimization using regression trees and linear models as integer programs. Artif. Intell. 244, 368\u2013395 (2017)","journal-title":"Artif. Intell."},{"key":"9736_CR46","unstructured":"Vinyals, O., Blundell, C., Lillicrap, T., Kavukcuoglu, K., Wierstra, D.: Matching networks for one shot learning. In: Proceedings of the 30th Conference on Neural Information Processing Systems, pp 3637\u20133645 (2016)"},{"issue":"5","key":"9736_CR47","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1142\/S0218213008004175","volume":"17","author":"X-H Vu","year":"2008","unstructured":"Vu, X.-H., O\u2019Sullivan, B.: A unifying framework for generalized constraint acquisition. Int. J. Artif. Intell. Tools 17(5), 803\u2013833 (2008)","journal-title":"Int. J. Artif. Intell. Tools"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09736-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-021-09736-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09736-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T15:39:53Z","timestamp":1671896393000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-021-09736-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,17]]},"references-count":47,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["9736"],"URL":"https:\/\/doi.org\/10.1007\/s10472-021-09736-4","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,17]]},"assertion":[{"value":"1 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}