Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization
BATURAY YILMAZ, ESRA ERDEM · 2025
Read Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization by BATURAY YILMAZ, ESRA ERDEM (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20013.txt.
Introduction
Baturay Yilmaz and Esra Erdem build a generator for hard stable roommates benchmark problems with many solutions. The roommates problem pairs people so no two would rather switch. Fair variants that maximize total satisfaction are hard to solve.
Random generators often yield no stable matching at all. When matchings exist, they are often few and easy to list. Listing then makes the fair variant simple in practice. The new algorithm targets instances rich in stable matchings. In such cases fair solutions resist simple enumeration. That hardness makes them honest tests for solvers. The study supplies tougher benchmarks for matching research. It helps separate real solver strength from easy cases.
Catalog record
| CREATOR | BATURAY YILMAZ, ESRA ERDEM |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20013
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization BATURAY YILMAZ, ESRA ERDEM Abstract 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. keywords benchmark instance generation, stable roommates problem, answer set programming 1 Introduction Benchmark instances play an important role in empirical analysis of methods, and thus the generation of meaningful and/or hard benchmark instances have been studied for various problems in AI ( Selman et al., 1996 ; Prosser, 2014 ; Torralba et al., 2021 ; Dang et al., 2022 ) and OR ( Pisinger, 2005 ; Vanhoucke and Maenhout, 2009 ) . In this study, we are interested in generating hard and meaningful benchmark instances for the stable roommates problem possibly with incomplete preference lists (SRI) ( Gale and Shapley, 1962 ; Gusfield and Irving, 1989 ) . In SRI, each agent provides a strictly ordered and possibly incomplete list of their preferences over the other agents, and the goal is to find a roommate for each agent (if possible) so that no two agents prefer each other more than their current roommates. SRI (unlike the stable marriage problem) might admit no solutions ( Gale and Shapley, 1962 ) . The existence of a stable matching for SRI can be decided in polynomial time ( Gusfield and Irving, 1989 ) . On the other hand, SRI with some fairness criteria become intractable. For instance, Egalitarian SRI, which tries to maximize the total satisfaction of agents if a stable matching exists, is NP-hard ( Feder, 1992 ; Cseh et al., 2019 ) . For experimental evaluations of methods to solve hard optimization variants of SRI (like the ASP-based methods in our earlier study ( Erdem et al., 2020 ) ), some well-known algorithms and tools have been used to randomly generate benchmark instances ( Gent and Prosser, 2002 ; Prosser, 2014 ) . For instance, we can randomly generate SRI instances using Prosser’s software ( SRItoolkit, 2019 ) that is based on Mertens’ idea ( Mertens, 2005 ) to generate a random graph ensemble G(n,p) according to the Erdös-Renyi model ( Erdös and Rényi, 1960 ), where n denotes the number of agents and p denotes the probability of the mutual acceptability of pairs of agents. Although such benchmark generators are useful for understanding various aspects of methods to solve SRI instances, they may not be sufficient for a thorough and controlled experimental evaluation of methods for hard variants of SRI, due to the following challenges we have observed in our studies and real-world applications ( Fidan and Erdem, 2021 ) . Challenge 1. The SRI benchmark instances randomly generated by the existing methods usually have a small number of stable matchings if one exists. For instance, the benchmark instances generated for empirical analysis by Erdem et al., 2020 ( Erdem et al., 2020 ) have less than 4 stable matchings in average. In such cases, an egalitarian stable matching can be found naively by enumerating all stable matchings. As Prosser notes ( Prosser, 2014 ): “Therefore, although NP-hard, we would fail to encounter a hard instance in the problems sampled. So, (as Cheeseman, Kanefsky and Taylor famously asked ( Cheeseman et al., 1991 )) where are the hard problems?” With the existing methods, generating hard instances for optimization variants of SRI, in the spirit of Prosser’s discussions (i.e., with too many stable matchings that is hard to enumerate), is challenging. Challenge 2. SRI (unlike the stable marriage problem) might admit no solutions ( Gale and Shapley, 1962 ) , and the SRI benchmark instances randomly generated by the existing methods are not always satisfiable. For instance, almost half of the the benchmark instances generated for empirical analysis by Erdem et al., 2020 ( Erdem et al., 2020 ) for 80 agents, do not have a stable matching. On the other hand, for controlled empirical analysis, it is desirable to be able to generate instances that have stable matchings. Ensuring the satisfiability of instances while generating them using the existing methods is challenging. Challenge 3. To investigate the applicability of the proposed methods for SRI in the real-world, it is desirable that the instances are also meaningful. For instance, in a real-world application of SRI at a university, it would not be meaningful to request long and strictly-ordered preference lists from students; usually, the preference lists would be short (e.g., containing 3–5 choices) and might include ties (SRTI). Generation of such meaningful SRTI instances by the existing methods is challenging. In this study, motivated by these three challenges and the need for useful benchmark instances for empirical studies of SRTI, our contributions can be summarized as follows: Contribution 1. We introduce a method to generate hard benchmark instances for SRI possibly with Ties, that have large number of (e.g., over 10^{6} ) stable matchings, and for which it would not be practical to find an optimal (e.g., egalitarian) stable matching by enumerating all stable matchings. Contribution 2. We introduce a “seed & combine” methodology underlying our method: (1) we generate small yet hard “seed” instances with respect to desired features, and (2) we construct large instances by “combining” these difficult seeds intelligently. Contribution 3. For (1), we utilize answer set programming (ASP) ( Marek and Truszczyński, 1999 ; Niemelä, 1999 ; Lifschitz, 2002 ; Brewka et al., 2011 ; Brewka et al., 2016 ) —a declarative programming paradigm based on answer set semantics ( Gelfond and Lifschitz, 1991 ; Gelfond and Lifschitz, 1988 ) , due to its expressive knowledge representation languages and efficient solvers. For (2), we introduce a novel algorithm. We illustrate the usefulness of our method with examples, and conclude with a discussion on its applicability to egalitarian one-to-one stable matching problems in general. 2 Generating Solvable Hard Seed Instances Our first objective is to generate “seed” SRTI instances that are small (i.e., with small number of agents and with short preference lists) yet that are hard in the spirit of Prosser (i.e., that have very large number of stable matchings). 2.1 Problem definition: seed-srti-sat We consider the definition of SRTI and Egalitarian SRTI as in our earlier study ( Erdem et al., 2020 ) . Let us briefly remind the relevant definitions. An SRTI instance is characterized by a nonempty set A of agents, and a collection \prec of preference lists \prec_{x}