{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:00:51Z","timestamp":1747173651913,"version":"3.40.5"},"reference-count":47,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T00:00:00Z","timestamp":1589155200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer set programming (ASP) is a paradigm for modeling knowledge-intensive domains and solving challenging reasoning problems. In ASP solving, a typical strategy is to preprocess problem instances by rewriting complex rules into simpler ones. Normalization is a rewriting process that removes extended rule types altogether in favor of normal rules. Recently, such techniques led to optimization rewriting in ASP, where the goal is to boost answer set optimization by refactoring the optimization criteria of interest. In this paper, we present a novel, general, and effective technique for optimization rewriting based on comparator networks which are specific kinds of circuits for reordering the elements of vectors. The idea is to connect an ASP encoding of a comparator network to the literals being optimized and to redistribute the weights of these literals over the structure of the network. The encoding captures information about the weight of an answer set in auxiliary atoms in a structured way that is proven to yield exponential improvements during branch-and-bound optimization on an infinite family of example programs. The used comparator network can be tuned freely, for example, to find the best size for a given benchmark class. Experiments show accelerated optimization performance on several benchmark problems.<\/jats:p>","DOI":"10.1017\/s147106842000006x","type":"journal-article","created":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T08:20:45Z","timestamp":1589185245000},"page":"512-551","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Boosting Answer Set Optimization with Weighted Comparator Networks"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9218-9562","authenticated-orcid":false,"given":"JORI","family":"BOMANSON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TOMI","family":"JANHUNEN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,5,11]]},"reference":[{"key":"S147106842000006X_ref14","unstructured":"Bomanson, J. and Janhunen, T. 2013. Normalizing cardinality rules using merging and sorting constructions. In Proceedings of LPNMR 2013. LNCS, vol. 8148. Springer, 187\u2013199."},{"key":"S147106842000006X_ref30","unstructured":"Gebser, M. , Maratea, M. and Ricca, F. 2017. The design of the seventh answer set programming competition. See Balduccini and Janhunen (2017), 3\u20139."},{"key":"S147106842000006X_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"S147106842000006X_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S147106842000006X_ref1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3653"},{"key":"S147106842000006X_ref17","unstructured":"Calimeri, F. , Faber, W. , Gebser, M. , Ianni, G. , Kaminski, R. , Krennwallner, T. , Leone, N. , Ricca, F. and Schaub, T. 2013. ASP-Core-2: 4th ASP Competition official input language format. URL: http:\/\/www.mat.unical.it\/aspcomp2013\/files\/ASP-CORE-2.01c.pdf."},{"key":"S147106842000006X_ref38","unstructured":"Lifschitz, V. and Razborov, A. A. 2006. Why are there so many loop formulas? ACM Transactions on Computational Logic 7, 2, 261\u2013268."},{"key":"S147106842000006X_ref45","unstructured":"Saikko, P. , Dodaro, C. , Alviano, M. and J\u00e4rvisalo, M. 2018. A hybrid approach to optimization in answer set programming. In Proceedings of KR 2018, Thielscher, M. , Toni, F. , and Wolter, F. , Eds. AAAI Press, 32\u201341."},{"key":"S147106842000006X_ref23","unstructured":"Dovier, A. and Santos Costa, V. , Eds. 2012. Technical Communications of ICLP 2012, vol. 17. Leibniz International Proceedings in Informatics (LIPIcs)."},{"key":"S147106842000006X_ref24","unstructured":"Drescher, C. and Walsh, T. 2012. Answer set solving with lazy nogood generation. See Dovier and Santos Costa (2012), 188\u2013200."},{"key":"S147106842000006X_ref22","unstructured":"Denecker, M. , Vennekens, J. , Bond, S. , Gebser, M. and Truszczy\u0144ski, M. 2009. The second answer set programming competition. In Proceedings of LPNMR 2009, Erdem, E. , Lin, F. and Schaub, T. , Eds. LNAI, vol. 5753. Springer, 637\u2013654."},{"key":"S147106842000006X_ref44","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"S147106842000006X_ref5","unstructured":"Andres, B. , Kaufmann, B. , Matheis, O. and Schaub, T. 2012. Unsatisfiability-based optimization in clasp. See Dovier and Santos Costa (2012), 212\u2013221."},{"key":"S147106842000006X_ref6","unstructured":"Anger, C. , Gebser, M. , Janhunen, T. and Schaub, T. 2006. What\u2019s a head without a body? In Proceedings of ECAI 2006. IOS Press, 769\u2013770."},{"key":"S147106842000006X_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000495"},{"key":"S147106842000006X_ref25","first-page":"1","article-title":"Translating Pseudo-Boolean constraints into SAT","volume":"1\u20134","author":"E\u00e9n","year":"2006","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation 2"},{"key":"S147106842000006X_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"},{"key":"S147106842000006X_ref20","unstructured":"Cussens, J. 2011. Bayesian network learning with cutting planes. In Proceedings of UAI 2011, Cozman, F. and Pfeffer, A. , Eds. AUAI Press, 153\u2013160."},{"key":"S147106842000006X_ref40","unstructured":"Maratea, M. , Pulina, L. and Ricca, F. 2015. Multi-level algorithm selection for ASP. See Calimeri et al. (2015), 439\u2013445."},{"key":"S147106842000006X_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-015-9611-4"},{"key":"S147106842000006X_ref2","unstructured":"Ab\u00edo, I. , Nieuwenhuis, R. , Oliveras, A. , Rodr\u00edguez-Carbonell, E. and Stuckey, P. J. 2013. To encode or to propagate? The best choice for each constraint in SAT. In Proceedings of CP 2013, C. Schulte, Ed. LNCS, vol. 8124. Springer, 97\u2013106."},{"key":"S147106842000006X_ref21","unstructured":"Davies, J. and Bacchus, F. 2011. Solving MAXSAT by solving a sequence of simpler SAT instances. In Proceedings of CP 2011, Lee, J. H. , Ed. LNCS, vol. 6876. Springer, 225\u2013239."},{"key":"S147106842000006X_ref3","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exv061"},{"key":"S147106842000006X_ref13","unstructured":"Bomanson, J. , Gebser, M. and Janhunen, T. 2016. Rewriting optimization statements in answer-set programs. In Technical Communications of ICLP 2016. OASIcs, vol. 52. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:15. Article 5."},{"key":"S147106842000006X_ref4","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exv061"},{"key":"S147106842000006X_ref11","unstructured":"Bomanson, J. 2017. lp2normal - A normalization tool for extended logic programs. See Balduccini and Janhunen (2017), 222\u2013228."},{"key":"S147106842000006X_ref26","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. , Romero, J. and Schaub, T. 2015. Progress in clasp series 3. See Calimeri et al. (2015), 368\u2013383."},{"key":"S147106842000006X_ref34","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2671"},{"key":"S147106842000006X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0707-0"},{"key":"S147106842000006X_ref27","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. , Ostrowski, M. , Schaub, T. , and Wanko, P. 2016. Theory solving made easy with clingo 5 (extended version). URL: http:\/\/www.cs.uni-potsdam.de\/wv\/publications\/."},{"key":"S147106842000006X_ref28","unstructured":"Gebser, M. , Kaufmann, B. and Schaub, T. 2012. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence 187, 52\u201389."},{"key":"S147106842000006X_ref41","unstructured":"MaxSAT-Comp. 2014. Ninth Max-SAT evaluation. URL: http:\/\/www.maxsat.udl.cat\/14\/."},{"key":"S147106842000006X_ref31","first-page":"1","article-title":"Tableau calculi for logic programs under answer set semantics","volume":"2","author":"Gebser","year":"2013","journal-title":"ACM Transactions on Computational Logic 14"},{"key":"S147106842000006X_ref8","unstructured":"Balduccini, M. and Janhunen, T. , Eds. 2017. Proceedings of LPNMR 2017. LNCS, vol. 10377. Springer."},{"key":"S147106842000006X_ref12","unstructured":"Bomanson, J. , Gebser, M. and Janhunen, T. 2014. Improving the normalization of weight rules in answer set programs. In Proceedings of JELIA 2014. LNCS, vol. 8761. Springer, 166\u2013180."},{"key":"S147106842000006X_ref7","unstructured":"Apt, K. , Blair, H. and Walker, A. 1987. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J. , Ed. Morgan Kaufmann Publishers, Chapter 2, 89\u2013148."},{"key":"S147106842000006X_ref32","unstructured":"Jaakkola, T. , Sontag, D. , Globerson, A. and Meila, M. 2010. Learning Bayesian network structure using LP relaxations. In Proceedings of AISTATS 2010. JMLR Proceedings, vol. 9. JMLR, 358\u2013365."},{"key":"S147106842000006X_ref42","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1139"},{"key":"S147106842000006X_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.03.004"},{"key":"S147106842000006X_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068408003578"},{"key":"S147106842000006X_ref47","unstructured":"Zhou, N. and Kjellerstrand, H. 2016. The picat-sat compiler. In Proceedings of PADL 2016, Gavanelli, M. and Reppy, J. H. , Eds. LNCS, vol. 9585. Springer, 48\u201362."},{"key":"S147106842000006X_ref29","unstructured":"Gebser, M. , Maratea, M. and Ricca, F. 2015. The design of the sixth answer set programming competition. See Calimeri et al. (2015), 531\u2013544."},{"key":"S147106842000006X_ref39","unstructured":"Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proceedings of ICLP 1994. MIT Press, 23\u201337."},{"key":"S147106842000006X_ref36","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000578"},{"key":"S147106842000006X_ref10","unstructured":"Batcher, K. E. 1968. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference. ACM, Thomson Book Company, 307\u2013314."},{"key":"S147106842000006X_ref18","unstructured":"Calimeri, F. , Ianni, G. and Truszczynski, M. , Eds. 2015. Proceedings of LPNMR 2015. LNCS, vol. 9345. Springer."},{"key":"S147106842000006X_ref43","unstructured":"Morgado, A. , Dodaro, C. and Marques-Silva, J. 2014. Core-guided maxsat with soft cardinality constraints. In Proceedings of CP 2014, B. O\u2019Sullivan, Ed. LNCS, vol. 8656. Springer, 564\u2013573."}],"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\/S147106842000006X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T09:34:00Z","timestamp":1612172040000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106842000006X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,11]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["S147106842000006X"],"URL":"https:\/\/doi.org\/10.1017\/s147106842000006x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2020,5,11]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}