AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (747.6 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

ILP-Based Heuristics for the Multi-Modal Stable Matching Problem

Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China, and are also with University of Chinese Academy of Sciences, Beijing 101408, China
School of Applied Mathematics and Computer Science, Technische Universität Berlin, Berlin 10623, Germany
School of Mathematics and Information Science, Hebei University, Baoding 071002, China
Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China
Show Author Information

Abstract

In this paper, we investigate the stable matching problem with multiple preferences in bipartite graphs, where each agent has various preference lists for all available partners with respect to different criteria. The problem requires that each matched agent must have exactly one partner and the obtained matching should be stable for all criteria. As our main contribution, we present an integer linear programming (ILP) model for determining whether there exists a globally stable matching in bipartite graphs, which has been proved to be NP-hard. Since the time consumed for solving ILPs might dramatically increase as the size of instances grows, we develop a preprocessing technique that helps to eliminate pairs that will never be a member of any globally stable matching and thus accelerates the computing process. We perform experiments on randomly generated preference lists and observe a significant speedup when we preprocess the instance before solving the ILPs. As there does not need to exist a perfect matching that is stable for all given criteria, we extend our ILP to the optimized version of the aforementioned problem, which asks to find a matching with maximum cardinality that is stable among all matched agents.

Keywords

stable matchingmulti-modalinteger linear programming (ILP)

References

[1]

D. Gale and L. S. Shapley, College admissions and the stability of marriage, Am. Math. Mon., vol. 69, no. 1, pp. 9–15, 1962.
Crossref Google Scholar
[2]

M. Balinski and T. Sönmez, A tale of two mechanisms: Student placement, J. Econ. Theory, vol. 84, no. 1, pp. 73–94, 1999.
Crossref Google Scholar
[3]

A. E. Roth, T. Sonmez, and M. U. Unver, Kidney exchange, Q. J. Econ., vol. 119, no. 2, pp. 457–488, 2004.
Crossref Google Scholar
[4]
S. Delong, A. Farhadi, R. Niazadeh, and B. Sivan, Online bipartite matching with reusable resources, in Proc. 23rd ACM Conf. Economics and Computation, Boulder, CO, USA, 2022, pp. 962–963.
Crossref
[5]
T. Ezra, M. Feldman, N. Gravin, and Z. G. Tang, General graphs are easier than bipartite graphs: Tight bounds for secretary matching, in Proc. 23rd ACM Conf. Economics and Computation, Boulder, CO, USA, 2022, pp. 1148–1177.
Crossref
[6]
D. Gusfield and R. W. Irving, The Stable Marriage Problem : Structure and Algorithms. Cambridge, MA, USA: MIT Press, 1989.
[7]

R. W. Irving and D. F. Manlove, The stable roommates problem with ties, J. Algoritms., vol. 43, no. 1, pp. 85–105, 2002.
Crossref Google Scholar
[8]
K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita, Stable marriage with incomplete lists and ties, in Proc. Automata, Languages and Programming 26th International Colloquium, ICALP'99, Prague, Czech Republic, 1999, pp. 443–452.
Crossref
[9]

Z. Király, Linear time local approximation algorithm for maximum stable marriage, Algorithms, vol. 6, no. 3, pp. 471–484, 2013.
Crossref Google Scholar
[10]
A. Kwanashie, Efficient algorithms for optimal matching problems under preferences, PhD dissertation, School of Computing Science, College of Science and Engineering, University of Glasgow, Glasgow, UK, 2015.
[11]
A. Kwanashie and D. F. Manlove, An integer programming approach to the hospitals/residents problem with ties, in Operations Research Proceedings 2013, D. Huisman, I. Louwerse, and A. Wagelmans, eds. Cham, Switzerland: Springer, 2014, pp. 263–269.
Crossref
[12]

M. Delorme, S. García, J. Gondzio, J. Kalcsics, D. Manlove, and W. Pettersson, Mathematical models for stable matching problems with ties and incomplete lists, Eur. J. Oper. Res., vol. 277, no. 2, pp. 426–441, 2019.
Crossref Google Scholar
[13]
J. Chen, R. Niedermeier, and P. Skowron, Stable marriage with multi-modal preferences, in Proc. 2018 ACM Conf. Economics and Computation, Ithaca, NY, USA, 2018, pp. 269–286.
Crossref
[14]

J. Chen, P. Skowron, and M. Sorge, Matchings under preferences: Strength of stability and Tradeoffs, ACM Trans. Econ. Comput., vol. 9, no. 4, pp. 1–55, 2021.
Crossref Google Scholar
[15]

R. Bredereck, J. Chen, D. Knop, J. Luo, and R. Niedermeier, Adapting stable matchings to evolving preferences, Proc. AAAI Conf. Artif. Intell., vol. 34, no. 2, pp. 1830–1837, 2020.
Crossref Google Scholar
[16]

J. H. Vande Vate, Linear programming brings marital bliss, Oper. Res. Lett., vol. 8, no. 3, pp. 147–153, 1989.
Crossref Google Scholar
[17]

R. W. Irving, An efficient algorithm for the “stable roommates” problem, J. Algoritms., vol. 6, no. 4, pp. 577–595, 1985.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 30 Issue 2,
April 2025
Pages 479-487
DOI: 10.26599/TST.2023.9010135
Cite this article:
Yang Y, Möhring RH, Song J, et al. ILP-Based Heuristics for the Multi-Modal Stable Matching Problem. Tsinghua Science and Technology, 2025, 30(2): 479-487. https://doi.org/10.26599/TST.2023.9010135

142

Views

44

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 30 June 2023
Revised: 04 September 2023
Accepted: 31 October 2023
Published: 09 December 2024
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return