{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:01:10Z","timestamp":1747173670719,"version":"3.40.5"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many industrial applications require finding solutions to challenging combinatorial problems. Efficient elimination of symmetric solution candidates is one of the key enablers for high-performance solving. However, existing model-based approaches for symmetry breaking are limited to problems for which a set of representative and easily solvable instances is available, which is often not the case in practical applications. This work extends the learning framework and implementation of a model-based approach for Answer Set Programming to overcome these limitations and address challenging problems, such as the Partner Units Problem. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system <jats:sc>ILASP<\/jats:sc>, redefine the learning task, and suggest a new example generation method to scale up the approach. The experiments conducted for different kinds of Partner Units Problem instances demonstrate the applicability of our approach and the computational benefits due to the first-order constraints learned.<\/jats:p>","DOI":"10.1017\/s1471068422000151","type":"journal-article","created":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T09:42:06Z","timestamp":1656582126000},"page":"606-622","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems"],"prefix":"10.1017","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6586-3649","authenticated-orcid":false,"given":"ALICE","family":"TARZARIOL","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0286-0958","authenticated-orcid":false,"given":"KONSTANTIN","family":"SCHEKOTIHIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTIN","family":"GEBSER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARK","family":"LAW","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,6,30]]},"reference":[{"key":"S1471068422000151_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000210"},{"key":"S1471068422000151_ref10","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-2011-0495"},{"key":"S1471068422000151_ref20","first-page":"57","article-title":"Inductive learning of answer set programs from noisy examples","volume":"7","author":"Law","year":"2018","journal-title":"Advances in Cognitive Systems"},{"key":"S1471068422000151_ref11","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2678"},{"key":"S1471068422000151_ref4","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/673"},{"key":"S1471068422000151_ref22","unstructured":"Law, M. , Russo, A. and Broda, K. 2021. ILASP. URL: https:\/\/www.ilasp.com. [Accessed on May 21, 2021]."},{"key":"S1471068422000151_ref7","unstructured":"Darga, P. , Katebi, H. , Liffiton, M. , Markov, I. and Sakallah, K. 2004. Saucy. URL: http:\/\/vlsicad.eecs.umich.edu\/BK\/SAUCY\/. [Accessed on May 21, 2021]."},{"year":"2005","author":"Puget","key":"S1471068422000151_ref26"},{"key":"S1471068422000151_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000284"},{"year":"2014","author":"Law","key":"S1471068422000151_ref19"},{"volume-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning","year":"2012","author":"Gebser","key":"S1471068422000151_ref14"},{"key":"S1471068422000151_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24658-7"},{"key":"S1471068422000151_ref28","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/284"},{"key":"S1471068422000151_ref27","unstructured":"Sakallah, K. 2009. Symmetry and satisfiability. In Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 289\u2013338."},{"key":"S1471068422000151_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-018-0548-6"},{"volume-title":"AAAI Conference on Artificial Intelligence","year":"2012","author":"Walsh","key":"S1471068422000151_ref32"},{"key":"S1471068422000151_ref13","unstructured":"Friedrich, G. , Ryabokon, A. , Falkner, A. , Haselb\u00d6ck, A. , Schenner, G. and Schreiner, H. (Re)configuration using answer set programming. In IJCAI 2011 Workshop on Configuration 2011, 17\u201324. CEUR-WS.org."},{"year":"2010","author":"Katebi","key":"S1471068422000151_ref17"},{"key":"S1471068422000151_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068422000151_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-006-8059-8"},{"year":"2008","author":"Mears","key":"S1471068422000151_ref25"},{"key":"S1471068422000151_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.12.004"},{"key":"S1471068422000151_ref30","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/284"},{"key":"S1471068422000151_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068422000011"},{"key":"S1471068422000151_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.10.008"},{"key":"S1471068422000151_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000508"},{"key":"S1471068422000151_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-020-05934-z"},{"key":"S1471068422000151_ref29","unstructured":"Tarzariol, A. , Gebser, M. and Schekotihin, K. 2022a. ILP Symmetry Breaking. URL: https:\/\/github.com\/prosysscience\/Symmetry_Breaking_with_ILP\/tree\/pup\/. [Accessed on January 28, 2022]."},{"volume-title":"AAAI Conference on Artificial Intelligence","year":"1994","author":"Crawford","key":"S1471068422000151_ref3"},{"year":"2011","author":"Aschinger","key":"S1471068422000151_ref1"},{"key":"S1471068422000151_ref5","unstructured":"Cropper, A. and Dumani, S. 2020. Inductive logic programming at 30: A new introduction. URL: https:\/\/arxiv.org\/abs\/2008.07912."},{"key":"S1471068422000151_ref33","doi-asserted-by":"crossref","unstructured":"Wilcoxon, F. 1992. Individual comparisons by ranking methods. In Breakthroughs in Statistics. Springer, 196\u2013202.","DOI":"10.1007\/978-1-4612-4380-9_16"},{"key":"S1471068422000151_ref21","unstructured":"Law, M. , Russo, A. and Broda, K. 2020. The ILASP system for inductive learning of answer set programs. URL: https:\/\/arxiv.org\/abs\/2005.00904."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068422000151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T23:40:25Z","timestamp":1680478825000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068422000151\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S1471068422000151"],"URL":"https:\/\/doi.org\/10.1017\/s1471068422000151","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}