{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:31:28Z","timestamp":1740123088344,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000},"content-version":"vor","delay-in-days":18,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"KWF project 28472"},{"name":"cms electronics GmbH"},{"name":"FunderMax GmbH"},{"name":"Hirsch Armb\u00e4nder GmbH"},{"name":"incubed IT GmbH"},{"name":"Infineon Technologies Austria AG"},{"name":"Isovolta AG"},{"name":"Kostwein Holding GmbH"},{"name":"Privatstiftung K\u00e4rntner Sparkasse"},{"DOI":"10.13039\/501100008905","name":"University of Klagenfurt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008905","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. Most of the existing approaches are instance-specific and focus on the automatic computation of Symmetry Breaking Constraints (SBCs) for each given problem instance. However, the application of such approaches to large-scale instances or advanced problem encodings might be problematic since the computed SBCs are propositional and, therefore, can neither be meaningfully interpreted nor transferred to other instances. As a result, a time-consuming recomputation of SBCs must be done before every invocation of a solver. To overcome these limitations, we introduce a new model-oriented approach for Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints using the Inductive Logic Programming paradigm. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs for a collection of combinatorial problems. The obtained results indicate that our approach significantly outperforms a state-of-the-art instance-specific method as well as the direct application of a solver.<\/jats:p>","DOI":"10.1007\/s10994-022-06146-3","type":"journal-article","created":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T19:15:07Z","timestamp":1650395707000},"page":"1303-1326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Lifting symmetry breaking constraints with inductive logic programming"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6586-3649","authenticated-orcid":false,"given":"Alice","family":"Tarzariol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Gebser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantin","family":"Schekotihin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,19]]},"reference":[{"issue":"2","key":"6146_CR1","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S1471068419000450","volume":"20","author":"F Calimeri","year":"2019","unstructured":"Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., & Schaub, T. (2019). ASP-Core-2 input language format. Theory and Practice of Logic Programming, 20(2), 294\u2013309.","journal-title":"Theory and Practice of Logic Programming"},{"key":"6146_CR2","doi-asserted-by":"crossref","unstructured":"Codenotti, P., Katebi, H., Sakallah, K., & Markov, I. (2013). Conflict analysis and branching heuristics in the search for graph automorphisms. In 25th IEEE International Conference on Tools with Artificial Intelligence, pp. 907\u2013914. IEEE Computer Society.","DOI":"10.1109\/ICTAI.2013.139"},{"issue":"2\u20133","key":"6146_CR3","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10601-006-8059-8","volume":"11","author":"D Cohen","year":"2006","unstructured":"Cohen, D., Jeavons, P., Jefferson, C., Petrie, K., & Smith, B. (2006). Symmetry definitions for constraint satisfaction problems. Constraints, 11(2\u20133), 115\u2013137.","journal-title":"Constraints"},{"key":"6146_CR4","doi-asserted-by":"crossref","unstructured":"Cropper, A., Duman\u010di\u0107, S., & Muggleton, S. (2020). Turning 30: New ideas in inductive logic programming. In 29th International Joint Conference on Artificial Intelligence, pp. 4833\u20134839. ijcai.org","DOI":"10.24963\/ijcai.2020\/673"},{"key":"6146_CR5","unstructured":"Cropper, A., & Duman\u010d\u0107, S. (2020). Inductive logic programming at 30: A new introduction. https:\/\/arxiv.org\/abs\/2008.07912"},{"key":"6146_CR6","unstructured":"Cropper, A., & Muggleton, S. (2016). Metagol. https:\/\/github.com\/metagol\/metagol"},{"key":"6146_CR7","unstructured":"Darga, P., Katebi, H., Liffiton, M., Markov, I., & Sakallah, K. (2004). Saucy http:\/\/vlsicad.eecs.umich.edu\/BK\/SAUCY\/"},{"issue":"5\u20136","key":"6146_CR8","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1017\/S1471068416000508","volume":"16","author":"J Devriendt","year":"2016","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M., & Denecker, M. (2016). On local domain symmetry for model expansion. Theory and Practice of Logic Programming, 16(5\u20136), 636\u2013652.","journal-title":"Theory and Practice of Logic Programming"},{"issue":"5\u20136","key":"6146_CR9","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1017\/S1471068416000284","volume":"16","author":"C Dodaro","year":"2016","unstructured":"Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F., & Schekotihin, K. (2016). Combining answer set programming and domain heuristics for solving hard industrial problems. Theory and Practice of Logic Programming, 16(5\u20136), 653\u2013669.","journal-title":"Theory and Practice of Logic Programming"},{"issue":"2","key":"6146_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.3233\/AIC-2011-0495","volume":"24","author":"C Drescher","year":"2011","unstructured":"Drescher, C., Tifrea, O., & Walsh, T. (2011). Symmetry-breaking answer set solving. AI Communications, 24(2), 177\u2013194.","journal-title":"AI Communications"},{"issue":"3","key":"6146_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1609\/aimag.v37i3.2678","volume":"37","author":"E Erdem","year":"2016","unstructured":"Erdem, E., Gelfond, M., & Leone, N. (2016). Applications of ASP. AI Magazine, 37(3), 53\u201368.","journal-title":"AI Magazine"},{"issue":"2\u20133","key":"6146_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s13218-018-0548-6","volume":"32","author":"A Falkner","year":"2018","unstructured":"Falkner, A., Friedrich, G., Schekotihin, K., Taupe, R., & Teppan, E. (2018). Industrial applications of answer set programming. K\u00fcnstliche Intelligenz, 32(2\u20133), 165\u2013176.","journal-title":"K\u00fcnstliche Intelligenz"},{"key":"6146_CR13","unstructured":"Friedrich, G., Ryabokon, A., Falkner, A., Haselb\u00f6ck, A., Schenner, G., & Schreiner, H. (2011). (Re)configuration using answer set programming. In: IJCAI 2011 Workshop on Configuration, pp. 17\u201324. CEUR-WS.org."},{"key":"6146_CR14","doi-asserted-by":"publisher","DOI":"10.2200\/S00457ED1V01Y201211AIM019","volume-title":"Answer set solving in practice","author":"M Gebser","year":"2012","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2012). Answer set solving in practice. Morgan and Claypool Publishers."},{"key":"6146_CR15","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF03037169","volume":"9","author":"M Gelfond","year":"1991","unstructured":"Gelfond, M., & Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9, 365\u2013385.","journal-title":"New Generation Computing"},{"key":"6146_CR16","unstructured":"Law, M. (2021). Conflict-driven inductive logic programming. https:\/\/arxiv.org\/abs\/2101.00058"},{"key":"6146_CR17","doi-asserted-by":"crossref","unstructured":"Law, M., Russo, A., Bertino, E., Broda, K., & Lobo, J. (2020). FastLAS: Scalable inductive logic programming incorporating domain-specific optimisation criteria. In: 34th National Conference on Artificial Intelligence , pp. 2877\u20132885. AAAI Press.","DOI":"10.1609\/aaai.v34i03.5678"},{"key":"6146_CR18","doi-asserted-by":"crossref","unstructured":"Law, M., Russo, A., & Broda, K. (2014). Inductive learning of answer set programs. In 14th European Conference on Logics in Artificial Intelligence , pp. 311\u2013325. Springer.","DOI":"10.1007\/978-3-319-11558-0_22"},{"issue":"5\u20136","key":"6146_CR19","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1017\/S1471068416000351","volume":"16","author":"M Law","year":"2016","unstructured":"Law, M., Russo, A., & Broda, K. (2016). Iterative learning of answer set programs from context dependent examples. Theory and Practice of Logic Programming, 16(5\u20136), 834\u2013848.","journal-title":"Theory and Practice of Logic Programming"},{"key":"6146_CR20","first-page":"57","volume":"7","author":"M Law","year":"2018","unstructured":"Law, M., Russo, A., & Broda, K. (2018). Inductive learning of answer set programs from noisy examples. Advances in Cognitive Systems, 7, 57\u201376.","journal-title":"Advances in Cognitive Systems"},{"key":"6146_CR21","unstructured":"Law, M., Russo, A., & Broda, K. (2021). Ilasp. http:\/\/www.ilasp.com"},{"key":"6146_CR22","doi-asserted-by":"crossref","unstructured":"Law, M., Russo, A., Broda, K., & Bertino, E. (2021). Scalable non-observational predicate learning in ASP. In 30th International Joint Conference on Artificial Intelligence , pp. 1936\u20131943. ijcai.org.","DOI":"10.24963\/ijcai.2021\/267"},{"key":"6146_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24658-7","volume-title":"Answer set programming","author":"V Lifschitz","year":"2019","unstructured":"Lifschitz, V. (2019). Answer set programming. Springer."},{"key":"6146_CR24","doi-asserted-by":"crossref","unstructured":"Margot, F. (2010). Symmetry in integer linear programming. In 50 Years of Integer Programming 1958\u20132008, pp. 647\u2013686. Springer-Verlag.","DOI":"10.1007\/978-3-540-68279-0_17"},{"key":"6146_CR25","doi-asserted-by":"crossref","unstructured":"Mears, C., Garc\u00eda de la Banda, M., Wallace, M., & Demoen, B. (2008). A novel approach for detecting symmetries in CSP models. In: 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems , pp. 158\u2013172. Springer.","DOI":"10.1007\/978-3-540-68155-7_14"},{"issue":"3\u20134","key":"6146_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF03037227","volume":"13","author":"S Muggleton","year":"1995","unstructured":"Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing, 13(3\u20134), 245\u2013286.","journal-title":"New Generation Computing"},{"key":"6146_CR27","doi-asserted-by":"crossref","unstructured":"Petrie, K., & Smith, B. (2003). Symmetry breaking in graceful graphs. In 9th International Conference on Principles and Practice of Constraint Programming , pp. 930\u2013934. Springer.","DOI":"10.1007\/978-3-540-45193-8_81"},{"key":"6146_CR28","doi-asserted-by":"crossref","unstructured":"Puget, J. (2005). Automatic detection of variable and value symmetries. In 11th International Conference on Principles and Practice of Constraint Programming, pp. 475\u2013489. Springer .","DOI":"10.1007\/11564751_36"},{"key":"6146_CR29","unstructured":"Sakallah, K. (2009). Symmetry and satisfiability. In: Handbook of satisfiability, pp. 289\u2013338. IOS Press."},{"key":"6146_CR30","unstructured":"Srinivasan, A. (2004). The Aleph manual. https:\/\/www.cs.ox.ac.uk\/activities\/programinduction\/Aleph\/."},{"key":"6146_CR31","unstructured":"Tarzariol, A., Gebser, M., & Schekotihin, K. (2021). ILP symmetry breaking. https:\/\/github.com\/prosysscience\/Symmetry_Breaking_with_ILP\/tree\/extended"},{"key":"6146_CR32","doi-asserted-by":"crossref","unstructured":"Tarzariol, A., Gebser, M., & Schekotihin, K. (2021). Lifting symmetry breaking constraints with inductive logic programming. In 30th International Joint Conference on Artificial Intelligence , pp. 2062\u20132068. ijcai.org.","DOI":"10.24963\/ijcai.2021\/284"},{"key":"6146_CR33","unstructured":"Walsh, T. (2012). Symmetry breaking constraints: Recent results. In 26th National Conference on Artificial Intelligence , pp. 2192\u20132198. AAAI Press."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06146-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06146-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06146-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T15:42:54Z","timestamp":1652802174000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06146-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["6146"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06146-3","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2022,4]]},"assertion":[{"value":"7 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}