{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:21:52Z","timestamp":1743135712611,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031604324"},{"type":"electronic","value":"9783031604331"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-60433-1_4","type":"book-chapter","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T05:03:34Z","timestamp":1717045414000},"page":"48-66","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["SATQUBOLIB: A Python Framework for\u00a0Creating and\u00a0Benchmarking (Max-)3SAT QUBOs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0894-8996","authenticated-orcid":false,"given":"Sebastian","family":"Zielinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5461-815X","authenticated-orcid":false,"given":"Magdalena","family":"Benkard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonas","family":"N\u00fc\u00dflein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6284-9286","authenticated-orcid":false,"given":"Claudia","family":"Linnhoff-Popien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2782-1469","authenticated-orcid":false,"given":"Sebastian","family":"Feld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,31]]},"reference":[{"key":"4_CR1","unstructured":"2011, S.C.: Sat competition 2011: Benchmark submission guidelines (2011). https:\/\/satcompetition.github.io\/2023\/benchmarks.html. Accessed 9 Feb 2024"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Abate, P., Di\u00a0Cosmo, R., Gousios, G., Zacchiroli, S.: Dependency solving is still hard, but we are getting better at it. In: 2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER), pp. 547\u2013551. IEEE (2020)","DOI":"10.1109\/SANER48275.2020.9054837"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational complexity: a modern approach. Cambrtidge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"4_CR4","unstructured":"Balyo, T., Heule, M., Iser, M., J\u00e4rvisalo, M., Suda, M. (eds.): Proceedings of SAT Competition 2023: Solver, Benchmark and Proof Checker Descriptions. Department of Computer Science Series of Publications B, Department of Computer Science, University of Helsinki, Finland (2023)"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10845-008-0203-4","volume":"21","author":"R Bart\u00e1k","year":"2010","unstructured":"Bart\u00e1k, R., Salido, M.A., Rossi, F.: Constraint satisfaction techniques in planning and scheduling. J. Intell. Manuf. 21, 5\u201315 (2010)","journal-title":"J. Intell. Manuf."},{"key":"4_CR6","unstructured":"Biere, A., Fleury, M.: Kissat homepage (2020). https:\/\/fmv.jku.at\/kissat\/ Accessed Feb 11 2024"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"37107","DOI":"10.1038\/srep37107","volume":"6","author":"N Chancellor","year":"2016","unstructured":"Chancellor, N., Zohren, S., Warburton, P.A., Benjamin, S.C., Roberts, S.: A direct mapping of max k-sat and high order parity checks to a chimera graph. Sci. Rep. 6(1), 37107 (2016)","journal-title":"Sci. Rep."},{"key":"4_CR8","unstructured":"Choi, V.: Adiabatic quantum algorithms for the np-complete maximum-weight independent set, exact cover and 3sat problems. arXiv preprint arXiv:1004.2226 (2010)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"4_CR10","unstructured":"Duan, Q., Al-Haj, S., Al-Shaer, E.: Provable configuration planning for wireless sensor networks. In: 2012 8th International Conference on Network and Service Management (cnsm) and 2012 Workshop on Systems Virtualiztion Management (svm), pp. 316\u2013321. IEEE (2012)"},{"key":"4_CR11","unstructured":"Escamocher, G., O\u2019Sullivan, B., Prestwich, S.D.: Generating difficult sat instances by preventing triangles. arXiv preprint arXiv:1903.03592 (2019)"},{"key":"4_CR12","unstructured":"Glover, F., Kochenberger, G., Du, Y.: A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538 (2018)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Gutin, G., Karapetyan, D.: Constraint branching in workflow satisfiability problem. In: Proceedings of the 25th ACM Symposium on Access Control Models and Technologies, pp. 93\u2013103 (2020)","DOI":"10.1145\/3381991.3395600"},{"key":"4_CR14","first-page":"283","volume":"2000","author":"HH Hoos","year":"2000","unstructured":"Hoos, H.H., St\u00fctzle, T.: Satlib: an online resource for research on sat. Sat 2000, 283\u2013292 (2000)","journal-title":"Sat"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/978-3-319-94144-8_26","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2018: 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9\u201312, 2018, Proceedings","author":"A Ignatiev","year":"2018","unstructured":"Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: a python toolkit for prototyping with SAT oracles. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) Theory and Applications of Satisfiability Testing \u2013 SAT 2018: 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9\u201312, 2018, Proceedings, pp. 428\u2013437. Springer International Publishing, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94144-8_26"},{"issue":"6","key":"4_CR16","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1145\/1993316.1993550","volume":"46","author":"M Jose","year":"2011","unstructured":"Jose, M., Majumdar, R.: Cause clue clauses: error localization using maximum satisfiability. ACM SIGPLAN Notices 46(6), 437\u2013446 (2011)","journal-title":"ACM SIGPLAN Notices"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1613\/jair.1.11339","volume":"66","author":"D Karapetyan","year":"2019","unstructured":"Karapetyan, D., Parkes, A.J., Gutin, G., Gagarin, A.: Pattern-based approach to the workflow satisfiability problem with user-independent constraints. J. Artif. Intell. Res. 66, 85\u2013122 (2019)","journal-title":"J. Artif. Intell. Res."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Kr\u00fcger, T., Mauerer, W.: Quantum annealing-based software components: An experimental case study with sat solving. In: Proceedings of the IEEE\/ACM 42nd International Conference on Software Engineering Workshops, pp. 445\u2013450 (2020)","DOI":"10.1145\/3387940.3391472"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Marques-Silva, J.P., Sakallah, K.A.: Boolean satisfiability in electronic design automation. In: Proceedings of the 37th Annual Design Automation Conference, pp. 675\u2013680 (2000)","DOI":"10.1145\/337292.337611"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"N\u00fc\u00dflein, J., Gabor, T., Linnhoff-Popien, C., Feld, S.: Algorithmic qubo formulations for k-sat and hamiltonian cycles. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 2240\u20132246 (2022)","DOI":"10.1145\/3520304.3533952"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"N\u00fc\u00dflein, J., Zielinski, S., Gabor, T., Linnhoff-Popien, C., Feld, S.: Solving (max) 3-sat via quadratic unconstrained binary optimization. arXiv preprint arXiv:2302.03536 (2023)","DOI":"10.1007\/978-3-031-36030-5_3"},{"issue":"2","key":"4_CR23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.75.026106","volume":"75","author":"F Radicchi","year":"2007","unstructured":"Radicchi, F., Vilone, D., Yoon, S., Meyer-Ortmanns, H.: Social balance as a satisfiability problem of computer science. Phys. Rev. E 75(2), 026106 (2007)","journal-title":"Phys. Rev. E"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Rintanen, J.: Planning as satisfiability: Heuristics. Artif. Intell. 193, 45\u201386 (2012)","DOI":"10.1016\/j.artint.2012.08.001"},{"issue":"12\u201313","key":"4_CR25","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1016\/j.artint.2006.08.002","volume":"170","author":"J Rintanen","year":"2006","unstructured":"Rintanen, J., Heljanko, K., Niemel\u00e4, I.: Planning as satisfiability: parallel plans and algorithms for plan search. Artif. Intell. 170(12\u201313), 1031\u20131080 (2006)","journal-title":"Artif. Intell."},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. Intell. 81(1\u20132), 17\u201329 (1996)","DOI":"10.1016\/0004-3702(95)00045-3"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134. IEEE (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"4_CR28","unstructured":"Spence, I.: Balanced random sat benchmarks. SAT Competition 2017, 53 (2017)"},{"key":"4_CR29","unstructured":"Verma, A., Lewis, M., Kochenberger, G.: Efficient qubo transformation for higher degree pseudo boolean functions. arXiv preprint arXiv:2107.11695 (2021)"},{"issue":"4","key":"4_CR30","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1109\/TC.2021.3063618","volume":"71","author":"M Zaman","year":"2021","unstructured":"Zaman, M., Tanahashi, K., Tanaka, S.: Pyqubo: Python library for mapping combinatorial optimization problems to qubo form. IEEE Trans. Comput. 71(4), 838\u2013850 (2021)","journal-title":"IEEE Trans. Comput."},{"key":"4_CR31","doi-asserted-by":"publisher","unstructured":"Zielinski, S., N\u00fc\u00dflein, J., Stein, J., Gabor, T., Linnhoff-Popien, C., Feld, S.: Influence of different 3sat-to-qubo transformations on the solution quality of quantum annealing: A benchmark study. In: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, pp. 2263\u20132271. GECCO \u201923 Companion, Association for Computing Machinery, New York, NY, USA (2023). https:\/\/doi.org\/10.1145\/3583133.3596330","DOI":"10.1145\/3583133.3596330"},{"key":"4_CR32","doi-asserted-by":"publisher","unstructured":"Zielinski, S., N\u00fc\u00dflein, J., Stein, J., Gabor, T., Linnhoff-Popien, C., Feld, S.: Pattern qubos: algorithmic construction of 3sat-to-qubo transformations. Electronics 12(16) (2023). https:\/\/doi.org\/10.3390\/electronics12163492, https:\/\/www.mdpi.com\/2079-9292\/12\/16\/3492","DOI":"10.3390\/electronics12163492"}],"container-title":["Communications in Computer and Information Science","Innovations for Community Services"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-60433-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T18:03:25Z","timestamp":1732125805000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-60433-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031604324","9783031604331"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-60433-1_4","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"I4CS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Innovations for Community Services","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mastricht","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"i4cs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.eah-jena.de\/i4cs-conference\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}