{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T08:40:02Z","timestamp":1751100002200,"version":"3.41.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031959721","type":"print"},{"value":"9783031959738","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-95973-8_11","type":"book-chapter","created":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T08:01:08Z","timestamp":1751097668000},"page":"169-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Breaking Symmetries from\u00a0a\u00a0Set-Covering Perspective"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0394-5854","authenticated-orcid":false,"given":"Michael","family":"Codish","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3487-784X","authenticated-orcid":false,"given":"Mikol\u00e1\u0161","family":"Janota","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 171\u2013183. ACM (1983)","DOI":"10.1145\/800061.808746"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/J.ARTINT.2014.07.011","volume":"216","author":"A Belov","year":"2014","unstructured":"Belov, A., Janota, M., Lynce, I., Marques-Silva, J.: Algorithms for computing minimal equivalent subformulas. Artif. Intell. 216, 309\u2013326 (2014). https:\/\/doi.org\/10.1016\/J.ARTINT.2014.07.011","journal-title":"Artif. Intell."},{"issue":"1\u20134","key":"11_CR3","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1023\/A:1019225027893","volume":"98","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper. Res. 98(1\u20134), 353\u2013371 (2000). https:\/\/doi.org\/10.1023\/A:1019225027893","journal-title":"Ann. Oper. Res."},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-319-90686-7_12","volume-title":"Functional and Logic Programming","author":"M Codish","year":"2018","unstructured":"Codish, M., Ehlers, T., Gange, G., Itzhakov, A., Stuckey, P.J.: Breaking symmetries with lex implications. In: Gallagher, J.P., Sulzmann, M. (eds.) FLOPS 2018. LNCS, vol. 10818, pp. 182\u2013197. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90686-7_12"},{"issue":"3","key":"11_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10601-016-9240-3","volume":"21","author":"M Codish","year":"2016","unstructured":"Codish, M., Frank, M., Itzhakov, A., Miller, A.: Computing the Ramsey number R(4, 3, 3) using abstraction and symmetry breaking. Constraints Int. J. 21(3), 375\u2013393 (2016)","journal-title":"Constraints Int. J."},{"key":"11_CR6","unstructured":"Codish, M., Miller, A., Prosser, P., Stuckey, P.J.: Breaking symmetries in graph representation. In: Rossi, F. (ed.) IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, 3\u20139 August 2013, pp. 510\u2013516. IJCAI\/AAAI (2013). http:\/\/ijcai.org\/proceedings\/2013"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10601-018-9294-5","volume":"24","author":"M Codish","year":"2018","unstructured":"Codish, M., Miller, A., Prosser, P., Stuckey, P.J.: Constraints for symmetry breaking in graph representation. Constraints 24(1), 1\u201324 (2018). https:\/\/doi.org\/10.1007\/s10601-018-9294-5","journal-title":"Constraints"},{"key":"11_CR8","unstructured":"Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A.: Symmetry-breaking predicates for search problems. In: Aiello, L.C., Doyle, J., Shapiro, S.C. (eds.) Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR 1996), Cambridge, Massachusetts, USA, 5\u20138 November 1996, pp. 148\u2013159. Morgan Kaufmann (1996)"},{"key":"11_CR9","unstructured":"Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A.: Symmetry-breaking predicates for search problems. In: Aiello, L.C., Doyle, J., Shapiro, S.C. (eds.) Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR 1996), pp. 148\u2013159. Morgan Kaufmann (1996)"},{"key":"11_CR10","unstructured":"Dan\u010do, M., Janota, M., Codish, M., Ara\u00fajo, J.J.: Complete symmetry breaking for finite models. In: AAAI 2025 (2025). https:\/\/arxiv.org\/abs\/2502.10155"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502\u2013518. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24605-3_37"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Elffers, J., Nordstr\u00f6m, J.: Divide and conquer: towards faster pseudo-boolean solving. In: Lang, J. (ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, 13\u201319 July 2018, Stockholm, Sweden, pp. 1291\u20131299. ijcai.org (2018). https:\/\/doi.org\/10.24963\/IJCAI.2018\/180","DOI":"10.24963\/IJCAI.2018\/180"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Frisch, A.M., Harvey, W.: Constraints for breaking all row and column symmetries in a three-by-two matrix. In: Proceedings of SymCon 2003 (2003)","DOI":"10.1007\/978-3-540-45193-8_22"},{"key":"11_CR14","doi-asserted-by":"publisher","unstructured":"Gauthier, T., Brown, C.E.: A formal proof of r(4, 5)=25. In: Bertot, Y., Kutsia, T., Norrish, M. (eds.) 15th International Conference on Interactive Theorem Proving, ITP 2024, 9\u201314 September 2024, Tbilisi, Georgia. LIPIcs, vol.\u00a0309, pp. 16:1\u201316:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ITP.2024.16","DOI":"10.4230\/LIPICS.ITP.2024.16"},{"key":"11_CR15","doi-asserted-by":"publisher","unstructured":"Gupta, A., Lee, E., Li, J.: A local search-based approach for set covering. In: Kavitha, T., Mehlhorn, K. (eds.) 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, 23\u201325 January 2023, pp. 1\u201311. SIAM (2023). https:\/\/doi.org\/10.1137\/1.9781611977585.CH1","DOI":"10.1137\/1.9781611977585.CH1"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Heule, M.J.H.: The quest for perfect and compact symmetry breaking for graph problems. In: Davenport, J.H., et al. (eds.) 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016, Timisoara, Romania, 24\u201327 September 2016, pp. 149\u2013156. IEEE Computer Society (2016). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=7827704","DOI":"10.1109\/SYNASC.2016.034"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s11786-019-00397-5","volume":"13","author":"MJH Heule","year":"2019","unstructured":"Heule, M.J.H.: Optimal symmetry breaking for graph problems. Math. Comput. Sci. 13, 533\u2013548 (2019)","journal-title":"Math. Comput. Sci."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Hoffman, K., Padberg, M.: Set covering, packing and partitioning problems, pp. 2348\u20132352. Springer, Boston (2001)","DOI":"10.1007\/0-306-48332-7_459"},{"issue":"3","key":"11_CR19","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10601-016-9244-z","volume":"21","author":"A Itzhakov","year":"2016","unstructured":"Itzhakov, A., Codish, M.: Breaking symmetries in graph search with canonizing sets. Constraints 21(3), 357\u2013374 (2016). https:\/\/doi.org\/10.1007\/s10601-016-9244-z","journal-title":"Constraints"},{"key":"11_CR20","doi-asserted-by":"publisher","unstructured":"Itzhakov, A., Codish, M.: Incremental symmetry breaking constraints for graph search problems. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02, pp. 1536\u20131543 (2020). https:\/\/doi.org\/10.1609\/aaai.v34i02.5513","DOI":"10.1609\/aaai.v34i02.5513"},{"issue":"2","key":"11_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.3233\/AIC-140640","volume":"28","author":"M Janota","year":"2015","unstructured":"Janota, M., Lynce, I., Marques-Silva, J.: Algorithms for computing backbones of propositional formulae. AI Commun. 28(2), 161\u2013177 (2015). https:\/\/doi.org\/10.3233\/AIC-140640","journal-title":"AI Commun."},{"key":"11_CR22","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held 20\u201322 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. The IBM Research Symposia Series. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"11_CR23","doi-asserted-by":"publisher","unstructured":"Lei, Z., Cai, S.: Solving set cover and dominating set via maximum satisfiability. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, 7\u201312 February 2020, pp. 1569\u20131576. AAAI Press (2020). https:\/\/doi.org\/10.1609\/AAAI.V34I02.5517","DOI":"10.1609\/AAAI.V34I02.5517"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"161232","DOI":"10.1109\/ACCESS.2020.3018618","volume":"8","author":"X Liu","year":"2020","unstructured":"Liu, X., Fang, Y., Chen, J., Su, Z., Li, C., L\u00fc, Z.: Effective approaches to solve p-center problem via set covering and sat. IEEE Access 8, 161232\u2013161244 (2020). https:\/\/doi.org\/10.1109\/ACCESS.2020.3018618","journal-title":"IEEE Access"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Marques-Silva, J., Janota, M., Belov, A.: Minimal sets over monotone predicates in boolean formulae. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification 25th International Conference, CAV 2013, Saint Petersburg, Russia, 13\u201319 July 2013. Proceedings. Lecture Notes in Computer Science, vol. 8044, pp. 592\u2013607. Springer (2013)","DOI":"10.1007\/978-3-642-39799-8_39"},{"key":"11_CR26","unstructured":"McGuire, G., Tugemann, B., Civario, G.: There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem. CoRR abs\/1201.0749 (2012). http:\/\/arxiv.org\/abs\/1201.0749"},{"key":"11_CR27","unstructured":"The on-line encyclopedia of integer sequences (2010). http:\/\/oeis.org"},{"key":"11_CR28","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0167-5060(08)70325-X","volume":"2","author":"RC Read","year":"1978","unstructured":"Read, R.C.: Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. Ann. Discrete Math. 2, 107\u2013120 (1978)","journal-title":"Ann. Discrete Math."},{"key":"11_CR29","doi-asserted-by":"publisher","unstructured":"Rintanen, J., Rankooh, M.F.: Symmetry-breaking constraints for directed graphs. In: Endriss, U., et al. (eds.) ECAI 2024 - 27th European Conference on Artificial Intelligence, 19\u201324 October 2024, Santiago de Compostela, Spain - Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024). Frontiers in Artificial Intelligence and Applications, vol.\u00a0392, pp. 4248\u20134253. IOS Press (2024). https:\/\/doi.org\/10.3233\/FAIA240998","DOI":"10.3233\/FAIA240998"},{"issue":"3","key":"11_CR30","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/OPRE.17.3.455","volume":"17","author":"R Roth","year":"1969","unstructured":"Roth, R.: Computer solutions to minimum-cover problems. Oper. Res. 17(3), 455\u2013465 (1969). https:\/\/doi.org\/10.1287\/OPRE.17.3.455","journal-title":"Oper. Res."},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Sharma, S., Roy, S., Soos, M., Meel, K.S.: GANAK: a scalable probabilistic exact model counter. In: Kraus, S. (ed.) Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 1169\u20131176. IJCAI, Macao, China (2019)","DOI":"10.24963\/ijcai.2019\/163"},{"issue":"12","key":"11_CR32","doi-asserted-by":"publisher","first-page":"1539","DOI":"10.1016\/j.dam.2005.10.018","volume":"155","author":"I Shlyakhter","year":"2007","unstructured":"Shlyakhter, I.: Generating effective symmetry-breaking predicates for search problems. Discret. Appl. Math. 155(12), 1539\u20131548 (2007)","journal-title":"Discret. Appl. Math."},{"key":"11_CR33","unstructured":"Tseitin, G.S.: On the complexity of derivations in the propositional calculus. Studies in Constructive Mathematics and Mathematical Logic (1968)"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Walsh, T.: General symmetry breaking constraints. In: Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, 25\u201329 September 2006, Proceedings, pp. 650\u2013664 (2006)","DOI":"10.1007\/11889205_46"}],"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-95973-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T08:01:12Z","timestamp":1751097672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-95973-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031959721","9783031959738"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-95973-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"29 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne, VIC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2025","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}