{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T13:00:19Z","timestamp":1761310819968,"version":"build-2065373602"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T00:00:00Z","timestamp":1756252800000},"content-version":"unspecified","delay-in-days":57,"URL":"https:\/\/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":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>While the existence of a stable matching for the stable roommates problem possibly with incomplete preference lists (SRI) can be decided in polynomial time, SRI problems with some fairness criteria are intractable. Egalitarian SRI that tries to maximize the total satisfaction of agents if a stable matching exists, is such a hard variant of SRI. For experimental evaluations of methods to solve these hard variants of SRI, several well-known algorithms have been used to randomly generate benchmark instances. However, these benchmark instances are not always satisfiable and usually have a small number of stable matchings if one exists. For such SRI instances, despite the NP-hardness of Egalitarian SRI, it is practical to find an egalitarian stable matching by enumerating all stable matchings. In this study, we introduce a novel algorithm to generate benchmark instances for SRI that have very large numbers of solutions, and for which it is hard to find an egalitarian stable matching by enumerating all stable matchings.<\/jats:p>","DOI":"10.1017\/s1471068425100240","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T09:34:48Z","timestamp":1756287288000},"page":"813-828","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization"],"prefix":"10.1017","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5030-0901","authenticated-orcid":false,"given":"BATURAY","family":"YILMAZ","sequence":"first","affiliation":[{"name":"Sabanci University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8384-7810","authenticated-orcid":false,"given":"ESRA","family":"ERDEM","sequence":"additional","affiliation":[{"name":"Sabanci University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"S1471068425100240_ref17","doi-asserted-by":"crossref","unstructured":"Marek, V. and Truszczy\u0144ski, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, 375\u2013398.","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068425100240_ref19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068425100240_ref4","unstructured":"Cheeseman, P. , Kanefsky, B. and Taylor, W. M. 1991. Where the really hard problems are. In Proceedings of IJCAI, 331\u2013337."},{"key":"S1471068425100240_ref20","first-page":"2271","article-title":"Where are the hard knapsack problems? Comput","volume":"32","author":"Pisinger","year":"2005","journal-title":"Operations Research"},{"key":"S1471068425100240_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000277"},{"key":"S1471068425100240_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90048-N"},{"key":"S1471068425100240_ref12","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP, 1070\u20131080."},{"key":"S1471068425100240_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9810-9"},{"key":"S1471068425100240_ref8","unstructured":"Erd\u00f6s, P. and R\u00e9nyi, A. 1960. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy f Sciences, 17\u201361."},{"key":"S1471068425100240_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068425100240_ref11","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"S1471068425100240_ref21","doi-asserted-by":"crossref","unstructured":"Prosser, P. 2014. Stable roommates and constraint programming. In Proceedings of CPAIOR, 15\u201328.","DOI":"10.1007\/978-3-319-07046-9_2"},{"key":"S1471068425100240_ref2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2669"},{"key":"S1471068425100240_ref14","unstructured":"Gent, I. P. and Prosser, P. 2022. An empirical study of the stable marriage problem with ties and incomplete lists. In Proceedings of the ECAI, 141\u2013145."},{"key":"S1471068425100240_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00045-3"},{"key":"S1471068425100240_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.03.044"},{"key":"S1471068425100240_ref3","doi-asserted-by":"crossref","unstructured":"Chakraborty, S. , Meel, K. S. and Vardi, M. Y. 2013. A scalable approximate model counter. In Proceedings of CP, 200\u2013216.","DOI":"10.1007\/978-3-642-40627-0_18"},{"key":"S1471068425100240_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00186-8"},{"key":"S1471068425100240_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"volume-title":"The Stable Marriage Problem: Structure and Algorithms","year":"1989","author":"Gusfield","key":"S1471068425100240_ref15"},{"key":"S1471068425100240_ref18","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/10\/P10008"},{"key":"S1471068425100240_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068421000302"},{"key":"S1471068425100240_ref23","unstructured":"SRItoolkit 2019. http:\/\/www.dcs.gla.ac.uk\/\u223cpat\/roommates\/distribution\/. [Accessed on November 21, 2019]"},{"key":"S1471068425100240_ref24","doi-asserted-by":"crossref","unstructured":"Torralba, \u00c1. , Seipp, J. and Sievers, S. 2021. Automatic instance generation for classical planning. In Proceedings of ICAPS, 376\u2013384.","DOI":"10.1609\/icaps.v31i1.15983"},{"key":"S1471068425100240_ref6","unstructured":"Dang, N. , Akg\u00fcn, O. , Espasa, J. , Miguel, I. and Nightingale, P. 2022. A framework for generating informative benchmark instances. In Proceedings of CP, Leibniz International Proc. in Informatics (LIPIcs), vol. 235, 18:1\u201318:18."}],"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\/S1471068425100240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T12:56:29Z","timestamp":1761310589000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068425100240\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S1471068425100240"],"URL":"https:\/\/doi.org\/10.1017\/s1471068425100240","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. 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 (https:\/\/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"}]}}