{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:04:41Z","timestamp":1743131081036,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031391439"},{"type":"electronic","value":"9783031391446"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-39144-6_10","type":"book-chapter","created":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T19:02:23Z","timestamp":1691089343000},"page":"149-166","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Symmetry and\u00a0Dominance Breaking for\u00a0Pseudo-Boolean Optimization"],"prefix":"10.1007","author":[{"given":"Daimy","family":"Van Caudenberg","sequence":"first","affiliation":[]},{"given":"Bart","family":"Bogaerts","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,4]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1278375","volume":"12","author":"FA Aloul","year":"2008","unstructured":"Aloul, F.A., Ramani, A., Markov, I.L., Sakallah, K.A.: Symmetry breaking for pseudo-boolean formulas. J. Expe. Algorithmics (JEA) 12, 1\u201314 (2008)","journal-title":"J. Expe. Algorithmics (JEA)"},{"key":"10_CR2","doi-asserted-by":"publisher","unstructured":"Aloul, F., Ramani, A., Markov, I., Sakallah, K.: Shatterpb: symmetry-breaking for pseudo-boolean formulas. In: ASP-DAC 2004: Asia and South Pacific Design Automation Conference 2004 (IEEE Cat. No. 04EX753), pp. 884\u2013887 (2004). https:\/\/doi.org\/10.1109\/ASPDAC.2004.1337720","DOI":"10.1109\/ASPDAC.2004.1337720"},{"issue":"5","key":"10_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/TC.2006.75","volume":"55","author":"FA Aloul","year":"2006","unstructured":"Aloul, F.A., Sakallah, K.A., Markov, I.L.: Efficient symmetry breaking for Boolean satisfiability. IEEE Trans. Comput. 55(5), 549\u2013558 (2006). https:\/\/doi.org\/10.1109\/TC.2006.75","journal-title":"IEEE Trans. Comput."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 684\u2013697 (2016)","DOI":"10.1145\/2897518.2897542"},{"key":"10_CR5","unstructured":"Benhamou, B., Nabhani, T., Ostrowski, R., Sa\u00efdi, M.R.: Dynamic symmetry breaking in the satisfiability problem. In: Proceedings of the 16th International Conference on Logic for Programming, Artificial intelligence, and Reasoning. LPAR-16, Dakar, Senegal (2010)"},{"key":"10_CR6","doi-asserted-by":"publisher","unstructured":"Benhamou, B., Nabhani, T., Ostrowski, R., Sa\u00efdi, M.R.: Enhancing clause learning by symmetry in SAT solvers. In: Proceedings of the 2010 22Nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2010, vol. 1, pp. 329\u2013335. IEEE Computer Society, Washington, DC (2010). https:\/\/doi.org\/10.1109\/ICTAI.2010.55","DOI":"10.1109\/ICTAI.2010.55"},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF00881844","volume":"12","author":"B Benhamou","year":"1994","unstructured":"Benhamou, B., Sa\u00efs, L.: Tractability through symmetries in propositional calculus. J. Autom. Reason. 12(1), 89\u2013102 (1994)","journal-title":"J. Autom. Reason."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Bogaerts, B., Gocht, S., McCreesh, C., Nordstr\u00f6m, J.: Certified symmetry and dominance breaking for combinatorial optimisation. In: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, 22 February\u20131 March 2022, pp. 3698\u20133707. AAAI Press (2022). https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/20283","DOI":"10.1609\/aaai.v36i4.20283"},{"key":"10_CR9","unstructured":"Booth, K.S., Colbourn, C.J.: Problems polynomially equivalent to graph isomorphism. Technical report CS-77-04, Department of Computer Science, University of Waterloo (1979)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/978-3-642-33558-7_4","volume-title":"Principles and Practice of Constraint Programming","author":"G Chu","year":"2012","unstructured":"Chu, G., Stuckey, P.J.: A generic method for identifying and exploiting dominance relations. In: Milano, M. (ed.) CP 2012. LNCS, pp. 6\u201322. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33558-7_4"},{"key":"10_CR11","unstructured":"Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A.: Symmetry-breaking predicates for search problems. In: Principles of Knowledge Representation and Reasoning, pp. 148\u2013159. Morgan Kaufmann (1996)"},{"key":"10_CR12","doi-asserted-by":"publisher","unstructured":"Devriendt, J.: MIPLIB 0\u20131 instances in OPB format (2020). https:\/\/doi.org\/10.5281\/zenodo.3870965","DOI":"10.5281\/zenodo.3870965"},{"key":"10_CR13","unstructured":"Devriendt, J., Bogaerts, B.: BreakID: static symmetry breaking for ASP (system description). In: Bogaerts, B., Harrison, A. (eds.) Ninth workshop on Answer Set Programmin and Other Computing Paradigms: Proceedings, 2016, New York City, New York, USA, 16 October 2016, pp. 25\u201339 (2016). http:\/\/docs.google.com\/viewer?a=v &pid=sites &srcid=ZGVmYXVsdGRvbWFpbnxhc3BvY3AyMDE2fGd4OjU4NTA0YTc3N2VkYWYyMWM"},{"key":"10_CR14","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M.: BreakIDGlucose: on the importance of row symmetry in SAT. In: Proceedings of the Fourth International Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT) (2014). https:\/\/lirias.kuleuven.be\/handle\/123456789\/456639"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-319-66263-3_6","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2017","author":"J Devriendt","year":"2017","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M.: Symmetric explanation learning: effective dynamic symmetry handling for SAT. In: Gaspers, S., Walsh, T. (eds.) SAT 2017. LNCS, vol. 10491, pp. 83\u2013100. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66263-3_6"},{"key":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-319-40970-2_8","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"J Devriendt","year":"2016","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M., Denecker, M.: Improved static symmetry breaking for SAT. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 104\u2013122. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40970-2_8"},{"key":"10_CR17","doi-asserted-by":"publisher","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M., Denecker, M.: On local domain symmetry for model expansion. Theory Pract. Logic Program. 16(5\u20136), 636\u2013652 (2016). https:\/\/doi.org\/10.1017\/S1471068416000508. https:\/\/www.cambridge.org\/core\/article\/on-local-domain-symmetry-for-model-expansion\/96E8AB07EB4C02D502B68687B23AC21C","DOI":"10.1017\/S1471068416000508"},{"key":"10_CR18","doi-asserted-by":"publisher","unstructured":"Devriendt, J., Bogaerts, B., De Cat, B., Denecker, M., Mears, C.: Symmetry propagation: improved dynamic symmetry breaking in SAT. In: IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI 2012, Athens, Greece, 7\u20139 November 2012, pp. 49\u201356. IEEE Computer Society (2012). https:\/\/doi.org\/10.1109\/ICTAI.2012.16","DOI":"10.1109\/ICTAI.2012.16"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Devriendt, J., Gocht, S., Demirovi\u0107, E., Nordstr\u00f6m, J., Stuckey, P.J.: Cutting to the core of pseudo-boolean optimization: combining core-guided search with cutting planes reasoning. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 3750\u20133758 (2021)","DOI":"10.1609\/aaai.v35i5.16492"},{"issue":"2","key":"10_CR20","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.: Symmetry-breaking answer set solving. AI Commun. 24(2), 177\u2013194 (2011)","journal-title":"AI Commun."},{"key":"10_CR21","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":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-46135-3_31","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"P Flener","year":"2002","unstructured":"Flener, P., et al.: Breaking row and column symmetries in matrix models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 462\u2013477. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46135-3_31"},{"key":"10_CR23","unstructured":"Gent, I.P., Smith, B.M.: Symmetry breaking in constraint programming. In: Proceedings of ECAI-2000, pp. 599\u2013603. IOS Press (2000)"},{"key":"10_CR24","doi-asserted-by":"publisher","unstructured":"Grohe, M.: Fixed-point definability and polynomial time on graphs with excluded minors. In: 2010 25th Annual IEEE Symposium on Logic in Computer Science, pp. 179\u2013188 (2010). https:\/\/doi.org\/10.1109\/LICS.2010.22","DOI":"10.1109\/LICS.2010.22"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-642-40313-2_4","volume-title":"Mathematical Foundations of Computer Science 2013","author":"M Grohe","year":"2013","unstructured":"Grohe, M.: Logical and structural approaches to the graph isomorphism problem. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, p. 42. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40313-2_4"},{"key":"10_CR26","unstructured":"Heule, M., Keur, A., Maaren, H.V., Stevens, C., Voortman, M.: CNF symmetry breaking options in conflict driven SAT solving (2005)"},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-642-14186-7_11","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"H Katebi","year":"2010","unstructured":"Katebi, H., Sakallah, K.A., Markov, I.L.: Symmetry and satisfiability: an update. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 113\u2013127. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14186-7_11"},{"key":"10_CR28","doi-asserted-by":"publisher","unstructured":"Kirchweger, M., Szeider, S.: SAT modulo symmetries for graph generation. In: Michel, L.D. (ed.) 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), 25\u201329 October 2021. LIPIcs, vol. 210, pp. 34:1\u201334:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CP.2021.34","DOI":"10.4230\/LIPIcs.CP.2021.34"},{"key":"10_CR29","doi-asserted-by":"publisher","unstructured":"Lubiw, A.: Some NP-complete problems similar to graph isomorphism. SIAM J. Comput. 10(1), 11\u201321 (1981). https:\/\/doi.org\/10.1137\/0210002","DOI":"10.1137\/0210002"},{"key":"10_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-540-72788-0_6","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"I Lynce","year":"2007","unstructured":"Lynce, I., Marques-Silva, J.: Breaking symmetries in SAT matrix models. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 22\u201327. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72788-0_6"},{"key":"10_CR31","doi-asserted-by":"publisher","unstructured":"Mears, C., Garc\u00eda de la Banda, M., Demoen, B., Wallace, M.: Lightweight dynamic symmetry breaking. Constraints 1\u201348 (2013). https:\/\/doi.org\/10.1007\/s10601-013-9154-2","DOI":"10.1007\/s10601-013-9154-2"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-319-89960-2_6","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"H Metin","year":"2018","unstructured":"Metin, H., Baarir, S., Colange, M., Kordon, F.: CDCLSym: introducing effective symmetry breaking in SAT solving. In: Beyer, D., Huisman, M. (eds.) TACAS 2018. LNCS, vol. 10805, pp. 99\u2013114. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89960-2_6"},{"key":"10_CR33","unstructured":"Nordstr\u00f6m, J.: Supplementary material for cutting to the core of pseudo-boolean optimization: combining core-guided search with cutting planes reasoning (2022). https:\/\/www.csc.kth.se\/~jakobn\/publications\/CoreGuidedPB\/"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271\u20132284 (2005)","DOI":"10.1016\/j.cor.2004.03.002"},{"key":"10_CR35","unstructured":"Roussel, O.: Pseudo-boolean competition 2016 (2016). https:\/\/www.cril.univ-artois.fr\/PB16\/"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Sabharwal, A.: SymChaff: exploiting symmetry in a structure-aware satisfiability solver. Constraints 14(4), 478\u2013505 (2009)","DOI":"10.1007\/s10601-008-9060-1"},{"key":"10_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-642-02777-2_22","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"B Schaafsma","year":"2009","unstructured":"Schaafsma, B., Heule, M.J.H., van Maaren, H.: Dynamic symmetry breaking by simulating Zykov contraction. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 223\u2013236. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02777-2_22"},{"key":"10_CR38","unstructured":"Van Caudenberg, D.: Static symmetry and dominance handling for pseudo-Boolean optimization (2022). Bachelor thesis; Bogaerts, Bart (supervisor). https:\/\/www.bartbogaerts.eu\/MScBScStudents\/2022-Daimy\/BScThesisDaimy.pdf"},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"Van Caudenberg, D., Bogaerts, B.: Static symmetry and dominance breaking for pseudo-Boolean optimization. In: BNAIC\/BeNeLearn 2022 (2022)","DOI":"10.1007\/978-3-031-39144-6_10"},{"key":"10_CR40","unstructured":"Walsh, T.: Symmetry breaking constraints: recent results. CoRR abs\/1204.3348 (2012)"}],"container-title":["Communications in Computer and Information Science","Artificial Intelligence and Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-39144-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T12:00:22Z","timestamp":1702900822000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-39144-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031391439","9783031391446"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-39144-6_10","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"4 August 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"BNAIC\/Benelearn","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Benelux Conference on Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mechelen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Belgium","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"bnaic2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/bnaic2022.uantwerpen.be\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}